Three Quantities to Calculate
For a small graph, the definitions of connectivity parameters lead to practical calculations: list degrees, test vertex removals, and count the edges crossing vertex-set partitions. The main source of errors is treating these as interchangeable tests. Minimum degree is a local quantity; vertex connectivity concerns removal of vertices; edge connectivity concerns removal of edges.
Throughout, graphs are finite, undirected and simple. For \(G=(V,E)\), the order is \(n=|V|\), and the degree \(\deg(v)\) is the number of edges incident with \(v\). The minimum degree is \(\delta(G)=\min_{v\in V}\deg(v)\). A graph is connected if every pair of its vertices is joined by a path.
Here \(G-S\) is the graph obtained by deleting the vertices in \(S\) and all their incident edges. The “at most one vertex” clause ensures that the definition also gives a value for complete graphs, in which deleting vertices may never leave two or more disconnected vertices.
A vertex separator removes vertices, whereas an edge cut removes edges. For a one-vertex graph, the minimum degree is also \(0\). For a disconnected graph with at least two vertices, the degree definition still applies, and both global connectivity values are \(0\) by the stated conventions.
Two Exhaustive Calculation Procedures
To calculate \(\kappa(G)\) for a connected graph with at least two vertices, test vertex sets in increasing order of size. Start with the empty set. If it does not qualify, test every one-vertex set, then every two-vertex set, and continue until a qualifying set is found. Because the first qualifying size is the smallest one, it is \(\kappa(G)\). The procedure terminates: deleting all but one vertex leaves at most one vertex.
To calculate \(\lambda(G)\), consider each nonempty proper subset \(S\subset V\) and count the edges with one endpoint in \(S\) and the other in \(V\setminus S\). Write this boundary as \(\partial(S)\). The smallest value \(|\partial(S)|\) is \(\lambda(G)\).
Proof. First take a nonempty proper set \(S\). Deleting every edge in \(\partial(S)\) leaves no edge between \(S\) and \(V\setminus S\). Since both sets contain a vertex, the resulting graph is disconnected. Thus \(\partial(S)\) is an edge cut, and \(\lambda(G)\leq |\partial(S)|\) for every such \(S\).
Conversely, let \(F\) be an edge cut, so \(G-F\) is disconnected. Choose the vertex set \(S\) of one connected component of \(G-F\). It is nonempty and proper. Every edge of the original graph from \(S\) to \(V\setminus S\) must have been deleted; otherwise the component would have an edge to another component in \(G-F\). Hence \(\partial(S)\subseteq F\), so \(|\partial(S)|\leq |F|\). Taking a minimum over edge cuts gives \(\min_S|\partial(S)|\leq\lambda(G)\). Together, the two inequalities prove equality. If \(G\) is disconnected, some component has empty boundary, so the minimum is \(0\), agreeing with the convention \(\lambda(G)=0\). \(\square\)
This proposition justifies the boundary-counting procedure: it replaces a search through edge sets by a search through vertex subsets. Each partition \(S,V\setminus S\) is counted twice, once from each side, but both counts are the same, so one may list only one representative from each complementary pair.
Worked Calculations
Worked Example: A Path on Five Vertices
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). Calculate \(\delta(G)\), \(\kappa(G)\) and \(\lambda(G)\).
The degrees are \(\deg(1)=1\), \(\deg(2)=2\), \(\deg(3)=2\), \(\deg(4)=2\), and \(\deg(5)=1\). Therefore \(\delta(G)=\min\{1,2,2,2,1\}=1\).
For vertex connectivity, the empty deletion leaves the connected path. The one-vertex tests are:
| Deleted set \(S\) | Components or remaining graph | Qualifies? |
|---|---|---|
| \(\varnothing\) | One path component | No |
| \(\{1\}\) | Path \(2,3,4,5\) | No |
| \(\{2\}\) | Isolated \(1\), and path \(3,4,5\) | Yes |
| \(\{3\}\) | Path \(1,2\), and path \(4,5\) | Yes |
| \(\{4\}\) | Path \(1,2,3\), and isolated \(5\) | Yes |
| \(\{5\}\) | Path \(1,2,3,4\) | No |
The first qualifying size is \(1\), so \(\kappa(G)=1\). For edge connectivity, deleting any one edge disconnects the path. The four one-edge tests \(12,23,34,45\) leave component sizes \(1+4,2+3,3+2,4+1\), respectively. Thus each is an edge cut of size \(1\), and \(\lambda(G)=1\), since a connected graph has no edge cut of size \(0\).
Check: the minimum degree, vertex connectivity and edge connectivity are all \(1\). The degree calculation gives \(\min\{1,2,2,2,1\}=1\); deleting vertex \(2\) disconnects the graph; and deleting edge \(12\) disconnects it.
Worked Example: A Complete Graph Missing One Edge
Let \(G=(V,E)\), where \(V=\{1,2,3,4\}\) and \(E=\{12,13,23,14,24\}\). Thus the only absent pair is \(34\). Find all three quantities.
The degrees are \(3,3,2,2\), respectively, so \(\delta(G)=\min\{3,3,2,2\}=2\).
The graph is connected. Deleting any one vertex leaves a connected graph: deleting \(1\) leaves edges \(23,24\); deleting \(2\) leaves \(13,14\); deleting \(3\) leaves the triangle with edges \(12,14,24\); deleting \(4\) leaves the triangle with edges \(12,13,23\). Thus no set of size \(0\) or \(1\) qualifies. Deleting \(\{1,2\}\) leaves vertices \(3,4\) with no edge, which is disconnected. Therefore \(\kappa(G)=2\).
For edge connectivity, enumerate singleton sets and pairs; these represent all partitions because larger sets have complementary representatives of size at most two.
| Representative \(S\) | Edges in \(\partial(S)\) | \(|\partial(S)|\) |
|---|---|---|
| \(\{1\}\) | \(12,13,14\) | 3 |
| \(\{2\}\) | \(12,23,24\) | 3 |
| \(\{3\}\) | \(13,23\) | 2 |
| \(\{4\}\) | \(14,24\) | 2 |
| \(\{1,2\}\) | \(13,14,23,24\) | 4 |
| \(\{1,3\}\) | \(12,14,23\) | 3 |
| \(\{1,4\}\) | \(12,13,24\) | 3 |
| \(\{2,3\}\) | \(12,24,13\) | 3 |
| \(\{2,4\}\) | \(12,23,14\) | 3 |
| \(\{3,4\}\) | \(13,23,14,24\) | 4 |
The smallest boundary size in the table is \(2\), attained by \(\{3\}\) and \(\{4\}\). Hence \(\lambda(G)=2\). For example, deleting the two edges \(13,23\) isolates vertex \(3\).
Check: the cut \(\partial(\{3\})=\{13,23\}\) has size \(2\), while every representative partition in the table has boundary size at least \(2\). Thus the minimum is exactly \(2\).
Worked Example: Two Triangles Sharing a Vertex
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,ad,de,ea\}\). Calculate the three quantities. The two triangles have the single shared vertex \(a\).
The degree of \(a\) is \(4\), since its incident edges are \(ab,ac,ad,ae\). Each of \(b,c,d,e\) has degree \(2\). Therefore \(\delta(G)=\min\{4,2,2,2,2\}=2\).
The graph is connected before any deletion. Deleting \(a\) leaves the two components on \(\{b,c\}\) and \(\{d,e\}\), with edges \(bc\) and \(de\). Thus a one-vertex separator exists, and the empty set is not a separator, so \(\kappa(G)=1\).
To find \(\lambda(G)\), take any nonempty proper \(S\subset V\). At least one of the two triangles is split between \(S\) and \(V\setminus S\). Indeed, if neither triangle were split, all vertices of each triangle would be on one side; because the triangles share \(a\), both would be on the same side, contradicting that \(S\) is nonempty and proper. A split triangle has either one or two vertices on one side. In either case exactly two of its three edges cross the partition. Consequently every such boundary has at least two edges. The specific set \(S=\{b\}\) has \(\partial(S)=\{ab,bc\}\), of size \(2\). The minimum boundary size is therefore \(2\), and \(\lambda(G)=2\).
Check: the witness boundary has two edges, and the split-triangle argument proves no partition has a boundary of size \(0\) or \(1\). Hence \(\lambda(G)=2\), while deleting the shared vertex gives \(\kappa(G)=1\).
Why the Calculations Must Be Kept Separate
The examples show that the same graph can have different values for these parameters. In the two-triangle graph, \(\delta(G)=2\), \(\kappa(G)=1\), and \(\lambda(G)=2\). The vertex \(a\) is a single-vertex separator, but disconnecting the graph by edge deletion requires at least two edges. Degree counts incident edges at one vertex; it does not by itself identify a vertex separator or an edge cut.
A useful check for any calculation is to state a witness for the claimed value and a reason no smaller value works. For \(\kappa(G)\), a witness is a vertex set whose deletion disconnects the graph or leaves at most one vertex; the lower-bound check tests every smaller-size set. For \(\lambda(G)\), a witness is an edge cut, and the lower-bound check tests all partition boundaries or gives a general reason each has at least the claimed size.
Disconnected graphs and isolated vertices deserve explicit attention. If a graph has an isolated vertex and at least one other vertex, it is disconnected, so \(\kappa(G)=\lambda(G)=0\) under the conventions above. Its minimum degree is also \(0\). If a graph consists of one vertex, all three quantities are \(0\) by convention and by the degree definition. These cases should be handled before running a procedure that assumes the graph is connected.
Common Mistake
Wrong calculation: for the two-triangle graph, one might say “there is no bridge, so \(\kappa(G)=2\).” This mixes edge deletion with vertex deletion. The absence of a bridge concerns whether one edge can disconnect the graph, not whether one vertex can. Deleting \(a\) separates \(\{b,c\}\) from \(\{d,e\}\), so \(\kappa(G)=1\). The edge-cut calculation is separate: every partition boundary has at least two edges, and \(\partial(\{b\})=\{ab,bc\}\), so \(\lambda(G)=2\).
Another error is to report the size of a set without checking what remains. A vertex set qualifies only if its deletion leaves a disconnected graph or at most one vertex. An edge set qualifies only if deleting those edges disconnects the graph. In each case, verify the claimed witness by examining the remaining graph.
Check Your Understanding
For each problem, give the three values when requested and support connectivity values with a witness and a minimality check.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), calculate \(\delta(G)\), \(\kappa(G)\) and \(\lambda(G)\).
- For \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,cd\}\), calculate the three quantities. Which vertex deletion first disconnects the graph?
- Explain why listing \(|\partial(S)|\) for one representative from each complementary pair of nonempty proper subsets is enough to calculate \(\lambda(G)\).
- A graph has an isolated vertex and at least one other vertex. State \(\kappa(G)\) and \(\lambda(G)\) under the conventions in this tutorial, and explain why.
- Give an example, using an explicit vertex set and edge set, where a vertex separator has size \(1\) but no single edge deletion disconnects the graph.