Minimum Degree as a Connectivity Bound

Minimum Degree and Edge Connectivity

A graph can have many edges overall and still be easy to disconnect: a small set of edges may join two dense regions. Minimum degree gives a simple upper bound on how many edges are needed. Choose a vertex with as few incident edges as possible; deleting those edges isolates it. This idea links a local quantity, measured at one vertex, to a global quantity, measured over all ways of disconnecting the graph.

Throughout, graphs are finite, undirected and simple. For a nonempty graph \(G=(V,E)\), the degree \(\deg(v)\) of a vertex \(v\) is the number of edges incident with it. The minimum degree is the smallest of these degrees.

To define edge connectivity, a set \(F\subseteq E(G)\) is an edge cut if deleting its edges disconnects the graph. For a connected graph with at least two vertices, edge connectivity is the size of a smallest edge cut. We also use the convention \(\lambda(G)=0\) if \(G\) is disconnected: deleting no edges already leaves it disconnected. For a graph with one vertex, set \(\lambda(G)=0\) by convention. The empty graph has no minimum degree under the definition above, so the bound below is stated for nonempty graphs.

Edge Cuts as Boundaries

For a vertex set \(S\subseteq V(G)\), its edge boundary \(\partial_G(S)\) consists of the edges with one endpoint in \(S\) and the other in \(V(G)\setminus S\). If \(S\) is nonempty and proper, deleting this boundary removes every edge between the two sides. This makes boundaries a convenient way to describe cuts.

Proof. First take any nonempty proper vertex set \(S\). After deleting \(\partial_G(S)\), there is no edge from \(S\) to its nonempty complement. Thus the resulting graph is disconnected, and \(\partial_G(S)\) is an edge cut. It follows that \(\lambda(G)\le|\partial_G(S)|\) for each such \(S\).

Conversely, let \(F\) be an edge cut. If \(G-F\) is disconnected, choose the vertex set \(S\) of one of its connected components. Then \(S\) is nonempty and proper. Every edge of \(\partial_G(S)\) must belong to \(F\), since otherwise that edge would still join this component to a vertex outside it in \(G-F\). Hence \(|\partial_G(S)|\le|F|\). This also applies if \(G\) was already disconnected and \(F=\varnothing\): a component of \(G\) has empty boundary. Taking minima in the two inequalities proves the formula. \(\square\)

The Minimum-Degree Bound

Proof. If \(G\) has one vertex, then its minimum degree is \(0\) and our convention gives \(\lambda(G)=0\), so the bound holds. Now suppose \(G\) has at least two vertices. If \(G\) is disconnected, \(\lambda(G)=0\), while every degree is nonnegative; therefore \(0\le\delta(G)\).

It remains to consider connected \(G\) with at least two vertices. Choose a minimum-degree vertex \(v\), so \(\deg(v)=\delta(G)\). The boundary of the one-vertex set \(\{v\}\) consists exactly of all edges incident with \(v\). Consequently, \(|\partial_G(\{v\})|=\deg(v)=\delta(G)\). The boundary lemma says that this boundary is an edge cut, so the minimum size of an edge cut is at most its size: \(\lambda(G)\le\delta(G)\). This proves the bound in every case. \(\square\)

The proof identifies a particular cut: remove every edge incident with a minimum-degree vertex. In a connected graph with at least two vertices, this leaves that vertex isolated while at least one other vertex remains. The graph is therefore disconnected. The argument gives an upper bound, not a guarantee that this cut is the smallest possible one.

A Useful Immediate Case

Proof. The vertex of degree \(1\) shows that \(\delta(G)=1\): connectedness and the presence of at least two vertices rule out degree \(0\). By the theorem, \(\lambda(G)\le1\). Since the graph is connected, deleting zero edges does not disconnect it, so \(\lambda(G)\ge1\). Therefore \(\lambda(G)=1\). \(\square\)

This case illustrates how a local feature can determine the global edge connectivity exactly. More generally, the theorem only says that a small degree supplies a cut no larger than that degree. A different cut, such as the single bridge in the two-triangle example, can be smaller still.

Common Mistake: Treating the Bound as an Equality

A common error is to calculate the minimum degree and report it as the edge connectivity. For the graph with two triangles joined by \(34\), that would give the incorrect calculation \(\lambda(G)=\delta(G)=2\). But deleting \(34\) alone separates the triangles, so \(\lambda(G)\le1\); because the graph is connected, \(\lambda(G)\ge1\), and hence \(\lambda(G)=1\). The correct conclusion from the degree calculation alone is only \(\lambda(G)\le\delta(G)\).

Another useful distinction is between a vertex's degree and the size of an arbitrary cut. The edges incident with a vertex form one particular boundary, namely \(\partial_G(\{v\})\). Edge connectivity is the size of a smallest boundary over all nonempty proper vertex sets. A cut that splits a graph into larger pieces may be smaller than every singleton boundary.

• Use minimum degree to bound from above: select a vertex of degree \(\delta(G)\) and isolate it.
• Use a cut to establish a stronger upper bound: any explicitly exhibited edge cut gives \(\lambda(G)\) no larger than its size.
• Check connectedness: for a disconnected graph, \(\lambda(G)=0\) under the stated convention, even if its minimum degree is positive.