Proving that a 3 regular graph has edge connectivity equal to vertex connectivity.

Question

Was one of my homework problems in Graph theory. I got marked wrong by our teaching assistant on the solution below that I provided:

Note that any 3 regular graph can be constructed by drawing 2 cycles of 1/2 |V(G)| vertices, and connecting inner vertices with the outer ones. Thus, it is obvious that edge connectivity=vertex connectivity =3.

What's wrong with this proof?

Answer 1

It is not true that any $3$-regular graph can be constructed in this way, and it is not true that any $3$-regular graph has vertex or edge connectivity $3$.

First of all, you can take two $3$-regular components, and get a $3$-regular graph that's not connected at all.

Other examples are also possible. Here's an example with connectivity $1$, and here's one with connectivity $2$. They are also shown below:

As a hint to get started, since you should already know that vertex connectivity is at most the edge connectivity, which is at most the minimum degree, you have only a few things to check:

• If a $3$-regular graph has a vertex cut of order $1$, it also has an edge cut of size $1$.
• If a $3$-regular graph has a vertex cut of order $2$, it also has an edge cut of size $2$.

Draw a picture of each of these, and see if you can spot the edge cut. (You'll have two cases in the second bullet point, since the two vertices in the vertex cut may or may not be adjacent.)