Documentation

Reconstruction.ConnectedComponents

Reconstruction Conjecture — Connected Components #

The number of connected components and the property of being connected are reconstructible graph invariants.

Main definitions #

Main results #

Proof outline #

The number of connected components can be recovered from the deck via Kelly's Lemma. Let E_k be the edgeless graph on k vertices. Then s(E_k, G) = ∑_C C(|C|, k) where the sum is over connected components C. Since s(E_k, G) is reconstructible for k < n by Kelly's Lemma, this system of equations determines the multiset of component sizes, hence the number of components.

References #

source
def SimpleGraph.numComponents {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) :
ℕ

The number of connected components of a graph.

Equations
Instances For
    source
    theorem SimpleGraph.SameDeck.numComponents_eq {V : Type u_1} [Fintype V] [DecidableEq V] {G H : SimpleGraph V} [DecidableRel G.Adj] [DecidableRel H.Adj] (h : G.SameDeck H) (hV : 3 ≤ Fintype.card V) :
    G.numComponents = H.numComponents

    The number of connected components is reconstructible.

    The proof uses Kelly's Lemma: the number of induced copies of the edgeless graph on k vertices equals ∑_C C(|C|, k) summed over connected components C. For k = 1, ..., n-1, all these counts are reconstructible. This system of polynomial equations determines the multiset of component sizes, hence the number of components.

    source
    theorem SimpleGraph.SameDeck.connected {V : Type u_1} [Fintype V] {G H : SimpleGraph V} (h : G.SameDeck H) (hV : 3 ≤ Fintype.card V) (hconn : G.Connected) :
    H.Connected

    Connectivity is reconstructible. If G is connected and has the same deck as H (on ≥ 3 vertices), then H is connected.

    A graph is connected iff it has exactly one connected component. Since the number of components is reconstructible, connectivity follows.