Connectedness Is About Paths, Not Direct Edges
A graph can have very few edges and still allow a route between every pair of vertices. Conversely, even a graph with many edges can fail to connect one vertex to the rest. Connectedness records whether the edges, taken together, allow paths between all pairs. When a graph is given by vertex and edge lists, the task is to justify either that such paths exist for every pair or that some pair cannot be joined.
Throughout, graphs are finite and simple: they have no loops or multiple edges. A path is a sequence of distinct vertices in which each consecutive pair is an edge; its endpoints are the first and last vertices. A single vertex is regarded as a path of length zero from that vertex to itself. A walk may repeat vertices, whereas a path may not. The earlier result that any walk between two vertices can be shortened to a path lets us use a walk as evidence that a path exists.
For a graph with one vertex, there are no distinct pairs to test, so the condition is satisfied. The empty graph is excluded by the convention above; this avoids treating the absence of vertices as a meaningful connection. For a graph with at least two vertices, connectedness is a substantive requirement: every vertex must be reachable from every other by a path. A direct edge is not required.
Certifying Connectedness from an Edge List
A positive answer needs evidence for all pairs of vertices, not just a claim that the graph “looks connected.” One convenient strategy is to exhibit paths from a fixed vertex to every other vertex. For any two vertices, reverse one of those paths and follow the other to make a walk between them; the walk-to-path result then gives a path. Alternatively, one can list paths for every pair when the graph is small.
Worked Example: A Path Graph on Five Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). Decide whether \(G\) is connected. We can check every pair \(i<j\) by writing down the consecutive vertices from \(i\) to \(j\):
| Pair | Path | Edges used |
|---|---|---|
| \(1,2\) | \(1,2\) | \(12\) |
| \(1,3\) | \(1,2,3\) | \(12,23\) |
| \(1,4\) | \(1,2,3,4\) | \(12,23,34\) |
| \(1,5\) | \(1,2,3,4,5\) | \(12,23,34,45\) |
| \(2,3\) | \(2,3\) | \(23\) |
| \(2,4\) | \(2,3,4\) | \(23,34\) |
| \(2,5\) | \(2,3,4,5\) | \(23,34,45\) |
| \(3,4\) | \(3,4\) | \(34\) |
| \(3,5\) | \(3,4,5\) | \(34,45\) |
| \(4,5\) | \(4,5\) | \(45\) |
There are \(\binom{5}{2}=5\cdot4/2=10\) unordered pairs of distinct vertices, and the table gives a path for each of these ten pairs. Every listed step is one of the four edges in \(E\), and no path repeats a vertex. Thus \(G\) is connected.
Check: The vertex set has five vertices, so there are \(5\cdot4/2=10\) distinct unordered pairs to check. The table contains ten rows of pairs, and each row’s path uses only edges in the stated edge list.
A Partition Can Certify That Paths Do Not Exist
To prove that a graph is not connected, it is enough to find one pair with no path. In practice, a more systematic certificate is often available: divide the vertices into two nonempty sets and check that no edge joins the sets. A path starting in one set cannot get to the other, because its first step from one set to the other would have to use such an edge.
Proof. First suppose \(G\) is connected. Take any partition \(V=X\cup Y\) into nonempty disjoint sets. Choose \(x\in X\) and \(y\in Y\). By connectedness, there is an \(x\)-\(y\) path. Starting in \(X\) and ending in \(Y\), this path must have a first vertex in \(Y\). The edge immediately before that vertex has one endpoint in \(X\) and one in \(Y\), as required.
Conversely, suppose every such partition has an edge joining its two sets. We show that every pair of distinct vertices has a path. Fix distinct vertices \(u,v\in V\). Let \(X\) consist of \(u\) and every vertex that can be reached from \(u\) by a path. Then \(X\) is nonempty. If \(v\notin X\), set \(Y=V\setminus X\); both sets would be nonempty. By the assumption, an edge \(xy\) would join some \(x\in X\) to some \(y\in Y\). There is a path from \(u\) to \(x\) by the definition of \(X\). Since \(y\notin X\), it is not a vertex of that path; appending the edge \(xy\) therefore gives a path from \(u\) to \(y\). This puts \(y\) in \(X\), a contradiction. Hence \(v\in X\), so there is a path from \(u\) to \(v\). The pair \(u,v\) was arbitrary, and \(G\) is connected. \(\square\)
Worked Example: A Disconnected Graph with an Isolated Vertex
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,cd\}\). The vertex \(e\) has no incident edge. Use a partition to decide whether \(G\) is connected.
Take \(X=\{a,b,c,d\}\) and \(Y=\{e\}\). The sets are disjoint, both are nonempty, and their union is \(V\). Check every edge: \(ab\) has both endpoints in \(X\), \(bc\) has both endpoints in \(X\), and \(cd\) has both endpoints in \(X\). Thus none of the three edges joins \(X\) to \(Y\). By the theorem, \(G\) is not connected. In particular, there is no path from \(e\) to \(a\).
Check: The edge list contains exactly \(ab,bc,cd\), and none has endpoint \(e\). Any path beginning at \(e\) would need a first edge incident with \(e\), but no such edge is present.
The same reasoning gives a useful quick test. If a graph has at least two vertices and one vertex is isolated (has degree zero), then it is not connected: choose the isolated vertex as one side of a partition and all other vertices as the other side. No edge crosses that partition.
Proof. Let \(u,v\) be any distinct vertices of \(G'\). Since \(G\) is connected, there is a path from \(u\) to \(v\) whose edges belong to \(E(G)\). The inclusion \(E(G)\subseteq E(G')\) means that every edge on this path also belongs to \(G'\). The same sequence of vertices is therefore a path from \(u\) to \(v\) in \(G'\). This holds for every distinct pair, so \(G'\) is connected. \(\square\)
Worked Example: Certifying Connectedness from a Short List of Paths
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,14,23,34,35,46,56\}\). Instead of writing paths for all fifteen pairs, find paths from vertex \(1\) to every other vertex.
The following sequences use only listed edges and have no repeated vertices:
- To \(2\): \(1,2\), using edge \(12\).
- To \(3\): \(1,2,3\), using edges \(12,23\).
- To \(4\): \(1,4\), using edge \(14\).
- To \(5\): \(1,2,3,5\), using edges \(12,23,35\).
- To \(6\): \(1,4,6\), using edges \(14,46\).
These paths connect \(1\) to each of the other five vertices. For any two distinct vertices \(u,v\), reverse the listed path from \(1\) to \(u\), then follow the listed path from \(1\) to \(v\). This gives a walk from \(u\) to \(v\). If vertices repeat in that walk, the walk-to-path result removes repetitions while keeping the endpoints. Therefore every pair is joined by a path, and \(G\) is connected.
Check: The five paths use, respectively, the edge sets \(\{12\}\), \(\{12,23\}\), \(\{14\}\), \(\{12,23,35\}\), and \(\{14,46\}\), all contained in \(E\). There are six vertices, so the pairwise test would require \(6\cdot5/2=15\) pairs; the paths from one fixed vertex establish all those pairs through walks, which can be shortened to paths.
Common Mistakes and Useful Checks
Confusing connected with complete. A complete graph has an edge between every pair of distinct vertices. A connected graph only requires a path, which may use several edges. For example, in the first example there is no edge \(15\), but \(1,2,3,4,5\) is a path from \(1\) to \(5\).
Checking only the edges that are listed. An edge list tells you which edges exist; an unlisted pair is not an edge. In the disconnected example, it would be incorrect to treat \(ae\) as an edge just because \(a\) and \(e\) are both vertices. The list contains no edge incident with \(e\), so there is no first step from \(e\).
Using too small a partition. A partition certificate must have two nonempty sides. For a graph with at least two vertices, a partition with no crossing edge proves disconnectedness. Merely naming a subset is not enough: check every edge and verify that none joins the subset to its complement.
For a positive answer, a fixed-vertex list of paths is often shorter than checking every pair separately. For a negative answer, a nonempty partition with no crossing edge is often shorter than trying to rule out every possible path one by one. In either case, the vertex set matters as much as the edge set: a vertex omitted from the edge list is still part of the graph if it appears in \(V\), and it may prevent the graph from being connected.
Check Your Understanding
For each question, use the stated vertex and edge sets and justify the answer with paths or a partition.
- Is the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\) connected? Give paths from one fixed vertex to the others.
- Is the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,cd\}\) connected? Give a partition that certifies your answer.
- Explain why a path from \(u\) to \(v\) need not consist of the single edge \(uv\).
- Prove that a graph with at least two vertices and an isolated vertex is not connected.
- If edges are added to a connected graph without changing its vertex set, can the resulting graph become disconnected? Justify your answer.