Let $G$ be a multigraph. A labeling assigns a natural number to every edge. A strict temporal path from $u$ to $v$ is a path from $u$ to $v$ in $G$ whose edge labels strictly increase in traversal order; the path of length zero is allowed. The labeled graph is temporally connected if, for every ordered pair of vertices $u, v$, there is a strict temporal path from $u$ to $v$. The instance $G$ of Gossiping is a yes-instance if some labeling makes $G$ temporally connected.

Interpreting each edge as a call between its endpoints and each label as the time of the call, a labeling is an ordering of the calls, and it is temporally connected exactly when every participant learns every secret.

Let $G$ be a multigraph and let $F$ be a set of edges of $G$; we identify $F$ with the spanning subgraph of $G$ that keeps all vertices of $G$ and only the edges in $F$. The components of $F$ are the connected components of this subgraph; every vertex of $G$ lies in a component, even if it is incident to no edge of $F$.

A set $F$ of edges is simple if it contains no loop and no two parallel edges. A simple set $F$ is acyclic if the subgraph it forms has no cycle, and it is a tree if it is acyclic and connected. A spanning tree of $G$ is a simple set of edges of $G$ forming a tree on all vertices of $G$. A spanning forest with $k$ components of $G$ is a simple acyclic set of edges of $G$ with exactly $k$ components.

A cycle of length $n ≥ 1$ consists of $n$ pairwise distinct vertices $v₀, …, vₙ₋₁$ and $n$ pairwise distinct edges $e₀, …, eₙ₋₁$ such that $eᵢ$ joins $vᵢ$ and $vᵢ₊₁$, with indices taken modulo $n$. Its edge set is ${e₀, …, eₙ₋₁}$.

Let $G$ be a multigraph. A labeling assigns a natural number to every edge. A strict temporal path from $u$ to $v$ is a path from $u$ to $v$ in $G$ whose edge labels strictly increase in traversal order; the path of length zero is allowed. The labeled graph is temporally connected if, for every ordered pair of vertices $u, v$, there is a strict temporal path from $u$ to $v$. The instance $G$ of Gossiping is a yes-instance if some labeling makes $G$ temporally connected.

Interpreting each edge as a call between its endpoints and each label as the time of the call, a labeling is an ordering of the calls, and it is temporally connected exactly when every participant learns every secret.

A $T$-witness of a multigraph $G$ is a pair of spanning trees of $G$ that share at most one edge. A multigraph is a $T$-graph if it has a $T$-witness.

An $M$-witness of a multigraph $G$ consists of pairwise edge-disjoint subgraphs $C$, $F₁$, $F₂$ of $G$, where $C$ is a cycle of length at least four and each $Fᵢ$ is a spanning forest of $G$ with exactly four components, each of which contains a vertex of $C$. A multigraph admits an $M$-witness if it has one, and it is an $M$-graph if it admits an $M$-witness and is not a $T$-graph.