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
• The prime quotient produced by the modular decomposition of a connected and anticonnected graph has at least four vertices Corollary
• C₆ and the disjoint union of two triangles have the same degree sequence but are not isomorphic Counterexample
• Maximal proper modules need not be disjoint when the graph or its complement is disconnected 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
• Walks, paths, connectedness and components in a simple graph on an arbitrary vertex set Definition
• Connected components, finite within-component distances, undefined cross-component distance and girth are computed in a disconnected graph Example
• For P₃-free graphs Rödl's theorem holds with δ=ε, by an explicit argument Example
• In a disjoint union of cliques of order k the whole vertex set is (k/n)-sparse Example
• P₄ is both connected and anticonnected Example
• Substituting into K₂ gives the join and substituting into K₂ gives the disjoint union Example
• Up to isomorphism the four-vertex path is the only prime graph on four vertices Example
• Every c-sparse set of size m contains a stable set of size at least m/2 False statement
• FALSE: a connected simple graph in which every vertex has even degree must itself be a cycle False statement
• A hatted-five-cycle-free rooted stable-tooth comb yields a large pure blockade of components Lemma
• A maximal acyclic spanning subgraph of a connected graph is a spanning tree Lemma
• A quotient block of connected or anticonnected blocks is again connected or anticonnected Lemma
• A vertex mixed on a connected set has opposite adjacency on some edge of that set 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 H₅-overlap class is connected Lemma
• Every plane triangulation with at least three vertices is connected Lemma
• Every union of connected components is a module, and so is every union of anticonnected components 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
• In a connected and anticonnected graph, the union of two proper modules that meet is again a proper module Lemma
• In a connected graph, some vertex outside a nonempty proper module is complete to it Lemma
• On a finite vertex set the graph notions agree, and on connected graphs the two path distances agree Lemma
• Swapping the two colours on one Kempe component preserves a proper colouring Lemma

…and 15 more results.

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

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