Cubic graphs

Task number: 3963

Show that each cubic (i.e. 3-regular) graph \(G\) satisfies \(k_v(G)=k_e(G)\).

  • 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.

Difficulty level: Moderate task
Proving or derivation task
Cs translation
Send comment on task by email