Connected Graphs

Graph Theory · Axiom Academy

Understanding connectivity and paths in graph theory 1. Formal Definition of Connectivity In other words, for any two vertices u and v in the graph, you can find a sequence of edges that connects them. If even one pair of vertices lacks a connecting path, the graph is disconnected . The animation below demonstrates connectivity testing by exploring paths from a starting vertex to all reachable vertices. 2. Equivalent Characterizations There are several equivalent ways to characterize graph connectivity. A graph G is connected if and only if any of the following conditions hold: Path existence: There exists a path between every pair of vertices Single component: The graph has exactly one connected component Reachability: Starting from any vertex, all other vertices are reachable Spanning tree: The graph contains a spanning tree (a tree that includes all vertices) These different perspectives are useful in different contexts. For example, algorithms often use the reachability characterization (via depth-first or breadth-first search), while theoretical proofs may use the spanning tree property. 3. Minimum Edges for Connectivity How many edges does a connected graph need? For a graph with n vertices, the minimum number of edges required for connectivity is exactly n - 1 . This minimum is achieved by tree structures. Trees are the "most economical" connected graphs - they use exactly n - 1 edges to connect n vertices, with no redundant connections.

This is the written version of the interactive lesson above. See the full Graph Theory course.