LemmaStatement: AI-adaptedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Complement of a disconnected graph is connected

PDF p. 2: Section 3, final sentence, complementation reduction

Statement

Let $G$ be a finite simple graph with at least two distinct connected components. Then its complement $\overline{G}$ is connected. A connected component is the induced subgraph on the vertices reachable by paths from a given vertex; a graph is connected when it is nonempty and every two of its vertices are joined by a path. The complement has the same vertex set as $G$ and has an edge between distinct vertices exactly when $G$ does not.

Statement references

A finite simple graph is a finite vertex set together with a set of two-element vertex subsets

Subgraphs, induced subgraphs and spanning subgraphs

Connected graphs and connected components defined by the existence of vertex paths

The connected components of a graph partition its vertex set and are its maximal connected subgraphs

Graph isomorphisms, automorphisms and graph complements

Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges

Facts & Assumptions

Given: A finite simple graph $G$ with at least two distinct connected components.

Goal: Prove that $\overline{G}$ is connected.

[F1]

The component vertex sets are nonempty, partition $V (G)$ , and consist of the vertices reachable by paths from their defining vertices (Connected graphs and connected components defined by the existence of vertex paths, The connected components of a graph partition its vertex set and are its maximal connected subgraphs).

[F2]

The complement has vertex set $V (G)$ ; distinct vertices are adjacent in it exactly when they are not adjacent in $G$ (Graph isomorphisms, automorphisms and graph complements, A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

[F3]

A path is a vertex list with distinct vertices and consecutive vertices adjacent. A single vertex is a path of length zero (Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges).

Proof

technique · direct

1.1F1F2F3

Vertices in distinct components cannot be adjacent in $G$ : an edge between them would be a path of length one, making them reachable from one another and hence members of the same component. Thus every pair of vertices in distinct components is adjacent in $\overline{G}$ .

2.1givenF1F3step 1.1

Let $x, y \in V (G)$ . If $x = y$ , the length-zero path joins them in $\overline{G}$ . If they lie in distinct components, their complement edge is a path joining them. If they are distinct and lie in the same component, choose a vertex $z$ in a different component, which exists and is nonempty. Then $x, z, y$ are distinct and both consecutive pairs are complement edges, so $(x, z, y)$ is a path in $\overline{G}$ .

3.1F1F2step 2.1∎

The vertex set of $\overline{G}$ is nonempty, since $G$ has a nonempty component, and every two of its vertices are joined by a path by step 2.1. Therefore $\overline{G}$ is connected.

Source notes

The article's complementation reduction uses this connectivity fact implicitly. The proof above is a local argument from the stated definitions and component partition, not a proof imported from the article.

Depends on

Used by · 1

Reduction to connected targets

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.

Sources

Maria Axenovich and Patrick Schmitteckert, Non-isomorphic graphs have distinct vertex-Ramsey classes, arXiv:2610.03704v1 · PDF p. 2, Section 3, final paragraph