## Cubic graphs

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.  