Collection of Maths Problems

Cubic graphs

Task number: 3963

• Solution

  We know that \( k_v (G) \le k_e (G) \).

  It is enough to argue the equality according to the growing vertex connectivity \( k_v (G) \).

  If \( k_v (G) = 1 \), \( G \) has an articulation. Once removed, the graph breaks down into at least two components. Because the articulation has degree 3, at least one of these components is connected by exactly one edge, i.e. \( k_e (G) = 1 \).

  We proceed similarly if \( G \) has a two-vertex cut \( \{u, v \} \). According to the same argument as in the previous case, exactly one edge leads from \( u \) to one of the components \( C \). If only one edge also connects \( C \) and \( v \), we have the edge cut we are looking for.

  Otherwise there are two edges between \( v \) and \( C \) two edges. \( G \) has after removal \( \{u, v \} \) two components \( C, C’ \) and \( u \) and \( v \) are not joined by an edge. The edges between \( u \) and \( C \) and between \( v \) and \( C’\) form the edge cut we are looking for.

  The minimum degree is the upper bound for edge and vertex connectivity, therefore in other cases the graph is vertex and edge 3-connected.

• Variant

  Prove that each bipartite cubic connected graph is necessarily vertex 2-connected.

• Solution

  By contradiction. If there is an articulation \( u \), its removal breaks down the graph into several components. The components are bipartite, on one side all the vertices are of degree 3, on the other one or two degrees two, the others have degree three.

  If we count the edges inside the component, we find that their number cannot be divisible by three and indivisible by three at the same time, which is a contradiction.