Structural Lemmas on Temporal Connectivity

Abstract

This paper presents several lemmas on the structure of temporal connectivity in temporal graphs. Some of these lemmas are adapted from the literature on gossip from the 70-90's and reformulated in the context of temporal graph theory. Many others are original. For ease of presentation and for avoiding lengthy case distinctions, we formulate all the lemmas in the setting of simple and proper (a.k.a, happy) temporal graphs, discussing occasionally their generality beyond this setting.