Cutting Edges

A cutting edge refers to an edge of a graph that uniquely connects two components of a graph \(G\). More precisely, a cutting edge \(e \in G\) must satisfy \(C(G) < C(G-e)\) where the function \(C(G)\) denotes the number of components of \(G\).

Proposition. An edge is a cutting edge if and only if it is contained in no cycles.

proof. For the forward direction, assume that an edge \(xy\) is a cutting edge, but is also included in some cycle \(v_1\dots v_n xy v_1\). From the cycle, we notice that \(x v_n \dots v_1 y\) is a closed path distinct from \(xy\). Removing the edge \(x, y\) will not affect the connectivity of the graph, for it is possible to rewrite \(xy\) as the listed path.

Now, suppose \(e = xy\) is not contained in any cycle but also not a cutting edge. The graph \(G – e\) has a path that connecting vertices \(x, y\). Construct the cycle by stitching the path with an extra edge. □

We present an interesting theorem that demonstrates the connectedness of even-degree graphs.

Theorem. If each vertex of a graph has an even degree, then the graph contains no cut edges.

proof. Restrict our attention to a single connected component of the graph and impose the condition that \(G\) in question is connected. We argue that each and every edge \(e=xy\) is contained in a cycle, hence is a cut edge. Since all vertices of \(G\) has an even degree, it is possible to extend a trail from one vertex to another. Let \(T\) be a collection of closed trails that include \(e\). Suppose none of the trails in \(T\) end in \(y\). The union of all trails are by itself a graph. Consider the graph \(\cup T – e\) with vertex \(y\) removed. By construction, all vertices of this graph, other than \(x\) has an even indegree since the trails can stretch out to all adjacent edges. However, \(x\) has an odd degree since the edge \(xy\) was deleted. Therefore, the sum of degrees in \(\cup T-e\) is odd, which is a contradiction. Necessarily there exists a trail from \(x\) to \(y\), and this trail can be reduced to generate a path. Connecting the path and edge \(xy\) creates the desired cycle. □