Common Errors in Connectivity Arguments

Three Distinctions That Prevent Connectivity Errors

Connectivity arguments often fail not because a difficult theorem has been misapplied, but because the claim quietly changes what is being deleted or what counts as a route. A vertex cut removes vertices; an edge cut removes edges. A walk may repeat vertices and edges, whereas a path does not repeat vertices. And having a path between every pair says only that a graph is connected: it does not say that several disjoint routes exist or that the graph remains connected after failures.

Throughout, graphs are finite and simple. A walk is a sequence of vertices in which consecutive vertices are adjacent. A path is a walk with no repeated vertices. A trail is a walk with no repeated edges. A graph is connected if every pair of distinct vertices is joined by a path. For a vertex set \(S\), \(G-S\) is the graph obtained by deleting the vertices in \(S\) and all incident edges; for an edge set \(F\), \(G-F\) is obtained by deleting just those edges.

These conventions handle the boundary cases explicitly. If a graph with at least two vertices is disconnected, the empty set is a vertex cut and an edge cut, so both parameters are zero. For a connected graph with at least two vertices, the empty set is neither. The condition “or has at most one vertex” in the vertex-cut definition is needed, for example, to give \(\kappa(K_n)=n-1\) for \(n\ge2\). The edge-cut definition does not need that clause: deleting edges does not change the vertex set, and a graph on at least two vertices with no edges is disconnected.

Vertex Cuts Are Not Edge Cuts

A vertex cut can remove every edge incident with a vertex all at once, while an edge cut counts those edges individually. It is therefore incorrect to transfer the size of a vertex cut directly to an edge cut. The two parameters measure different deletion operations, even when both describe ways to disconnect the same graph.

A related proof check is to name exactly what the deletion leaves behind. To show that \(S\) separates two specified vertices \(u,v\), the relevant claim is that \(G-S\) has no \(u\)-\(v\) path, with \(u,v\notin S\). To show that an edge set \(F\) disconnects the graph, the claim is that \(G-F\) is disconnected. A set may satisfy one of these conditions without satisfying the other.

A Walk Is Not Automatically a Path

Repeated vertices are permitted in a walk, but not in a path. This matters whenever the conclusion requires a path, or several paths with disjointness conditions: repeating a route does not create a second path, and a walk that revisits an edge cannot be counted as edge-disjoint from a route using that edge.

Proof. Let \(W=v_0,v_1,\ldots,v_\ell\) be a walk from \(v_0\) to \(v_\ell\), where \(v_0\ne v_\ell\). If no vertex is repeated, \(W\) is already a path. Otherwise choose indices \(i<j\) with \(v_i=v_j\). Delete the portion \(v_{i+1},\ldots,v_j\). The resulting sequence is still a walk with the same endpoints: if \(j<\ell\), the next edge is valid because \(v_i=v_j\) and \(v_jv_{j+1}\) was an edge; if \(j=\ell\), the new final vertex \(v_i\) equals the old endpoint \(v_\ell\). The length has decreased by \(j-i>0\). Repeat this operation whenever a vertex is repeated. Since the length is a nonnegative integer and decreases each time, the process terminates. The resulting walk has no repeated vertices and still joins \(v_0\) to \(v_\ell\), so it is a path. \(\square\)

The lemma allows a walk to establish that two vertices are connected, but it does not turn a repeated walk into multiple distinct or disjoint paths. The repeated portions must first be removed, and the resulting path may use edges that another proposed route uses as well.

Pairwise Routes Do Not Determine Global Connectivity

The statement “every pair of vertices is joined by a path” is precisely connectedness. It does not assert that every pair has several internally disjoint paths, and it does not rule out a vertex whose deletion disconnects the graph. Pair-specific connectivity counts routes for selected terminals; global connectivity records the smallest deletion that disconnects the graph (with the stated convention for leaving at most one vertex).

For nonadjacent vertices \(u,v\), one useful pair-specific quantity is the maximum number of \(u\)-\(v\) paths that are internally vertex-disjoint: no two of the paths share a vertex other than \(u\) or \(v\). This quantity concerns that particular pair. It should not be identified with \(\kappa(G)\), which concerns the most vulnerable deletion in the whole graph.

Proof. Suppose first that \(\kappa(G)=1\). By the definition of \(\kappa(G)\), there is a vertex cut \(S\) of size \(1\). Write \(S=\{v\}\). Since \(G\) has at least three vertices, \(G-v\) has at least two vertices; thus the “at most one vertex” alternative in the definition does not apply. The vertex-cut condition implies that \(G-v\) is disconnected, so \(v\) is an articulation vertex. Conversely, suppose \(v\) is an articulation vertex. Then \(G-v\) is disconnected, so \(\{v\}\) is a vertex cut and \(\kappa(G)\le1\). Because \(G\) is connected, the empty set is not a vertex cut; hence \(\kappa(G)\ne0\). It follows that \(\kappa(G)=1\). \(\square\)

The hypotheses matter. Connectedness excludes the case \(\kappa(G)=0\), and at least three vertices ensures that deleting one vertex does not leave a graph with only one vertex under the chosen convention. In particular, the theorem is not stated for \(K_2\), where \(\kappa(K_2)=1\) under our definition but neither vertex deletion leaves a disconnected graph.

How to Audit a Connectivity Claim

Before applying a connectivity theorem or reporting a parameter, identify the exact object being counted and the exact operation being performed. The following questions expose many common errors:

• Which objects are removed? If vertices are deleted, include their incident edges automatically; if only edges are deleted, keep all vertices.
• What does “separates” mean here? For fixed terminals, check that the separator excludes the terminals and that no path remains between them.
• Is the proposed route a path? List its vertices in order and check for repetitions before counting it as a path.
• Is the claim pair-specific or global? A collection of routes for one pair does not establish a lower bound on connectivity throughout the graph.
• Are the parameter’s boundary conventions covered? State the domain and convention, especially for disconnected graphs and \(K_1\).

A useful counterexample should be checked in both directions: verify the claimed deletion really disconnects the graph, and verify that every smaller deletion fails if a minimum is being asserted. In the two-triangle example, showing that deleting \(c\) disconnects proves only \(\kappa(G)\le1\); connectedness supplies the other inequality. Likewise, finding a two-edge cut proves only \(\lambda(G)\le2\); checking that no single edge disconnects supplies the lower bound.

When a proof uses disjoint paths as a certificate, inspect the disjointness condition itself. Internally vertex-disjoint paths may share their endpoints, but they may not share an internal vertex. Edge-disjoint paths may share vertices, but they may not share edges. The two notions are not interchangeable. The earlier material on Menger’s theorem gives precise path-packing and separator statements; these checks ensure that the objects supplied really meet the theorem’s hypotheses.