Proposition: Connectivity Is an Equivalence Relation - Components Are a Partition of a Graph

The connectivity of vertices of an directed or undirected graph \(G(V,E)\) is an equivalence relation "\(\leftrightarrow\)" on the set of all vertices \(V\).

In particular, the equivalence classes \(V'\in V/_\leftrightarrow\) build a partition of \(V\), and any vertex \(v\in V\) can be chosen as a representative of exactly one equivalence class \(V'\), such that the induced subgraph (respectively subdigraph) \(G[V']\) contains the vertex \(v\).

\(G[V']\) is called the component of the vertex \(v\).

Proofs: 1

Corollaries: 1
Definitions: 2
Examples: 3
Proofs: 4 5 6
Propositions: 7 8

Thank you to the contributors under CC BY-SA 4.0!




  1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition