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

Depends on

• Unless stated otherwise, graph means finite, simple and undirected; orders, sizes and empty-set conventions are fixed here
• Subgraphs, induced subgraphs and spanning subgraphs
• Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges
• Every walk between two vertices contains a path between the same endpoints

Used by

• A tree on n≥1 vertices has n-1 edges Corollary
• The connected components of a graph partition its vertex set and are its maximal connected subgraphs Corollary
• C₆ and the disjoint union of two triangles have the same degree sequence but are not isomorphic Counterexample
• The class of connected graphs is not hereditary Counterexample
• Two disjoint copies of Kₘ show that Dirac's bound cannot be lowered to n/2-1 for even n=2m≥4 Counterexample
• A bridge as an edge whose deletion increases the number of connected components Definition
• Anticonnected graphs and anticonnected components Definition
• Degree in a multigraph, indegree and outdegree in a digraph, and their underlying connectivity Definition
• Graph distance within a component, eccentricity, diameter and girth, including the acyclic convention Definition
• Hamilton paths, Hamilton cycles, Hamiltonian graphs and Hamilton-connected graphs Definition
• Kempe chains as connected components induced by two colour classes Definition
• Trees, forests, leaves and isolated vertices Definition
• Vertex cuts, edge cuts, vertex connectivity κ(G) and edge connectivity λ(G), with conventions for complete and one-vertex graphs Definition
• Connected components, finite within-component distances, undefined cross-component distance and girth are computed in a disconnected graph Example
• P₄ is both connected and anticonnected Example
• FALSE: a connected simple graph in which every vertex has even degree must itself be a cycle False statement
• A maximal acyclic spanning subgraph of a connected graph is a spanning tree Lemma
• An edge of a finite graph is a bridge if and only if it lies on no cycle Lemma
• Being joined by a walk or path is the same equivalence relation on the vertex set Lemma
• Deleting any edge of a tree separates it into exactly two tree components Lemma
• Every plane triangulation with at least three vertices is connected Lemma
• For every nontrivial connected graph, κ(G)≤λ(G) Lemma
• If two distinct faces of a connected plane graph have the same boundary subgraph, then the graph is a cycle Lemma
• Swapping the two colours on one Kempe component preserves a proper colouring Lemma
• The symmetric difference of two matchings is a disjoint union of alternating paths and even cycles Lemma
• A finite graph is bipartite if and only if it has no odd cycle Theorem
• A finite graph is connected if and only if it has a spanning tree Theorem
• An n-vertex simple graph with more than binomn-12 edges is connected Theorem
• Equivalent characterisations of a nonempty tree by unique paths, edge count, minimal connectivity and maximal acyclicity Theorem
• Every graph with at least two vertices is connected or anticonnected Theorem
• Gallai's identity: ν(G)+ρ(G)=|V(G)| when G has no isolated vertex Theorem
• If G has a Hamilton cycle, then deleting any nonempty proper vertex set S leaves at most |S| connected components Theorem

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 14 results over 10 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

• University of Lethbridge, Combinatorics: A Guided Tour, Paths and Cycles (standard reference, not scraped)