Does graph G with all vertices of degree 3 have a cut vertex?

Question

I'm asked to draw a simple connected graph, if possible, in which every vertex has degree 3 and has a cut vertex. I tried drawing a cycle graph, in which all the degrees are 2, and it seems there is no cut vertex there. I know, so far, that, by the handshaking theorem, the number of vertices have to be even and they have to be greater than or equal to 4. So, I kept drawing such graphs but couldn't find one with a cut vertex. I have a feeling that there must be at least one vertex of degree one but I don't know how to formally prove this, if its true. I'd appreciate if someone can help with that.

Answer 1

Not necessarily true, for example complete graph of 4 vertices have no cut vertex. But there exists a graph G with all vertices of degree 3 and there is a cut vertex. See the picture. Red vertex is the cut vertex.

Answer 2

when dealing with questions such as this, it's most helpful to think about how you could go about solving it.

An easy way to make a graph with a cutvertex is to take several disjoint connected graphs, add a new vertex and add an edge from it to each component: the new vertex is the cutvertex. We just need to do this in a way that results in a 3-regular graph.

You've been able to construct plenty of 3-regular graphs that we can start with. If we take three of them, then the "new vertex" above will have degree 3, which is good, but its neighbours will have degree 4, which isn't. However, if we can manufacture a degree-2 vertex in each component, we can join that vertex to the new vertex, and our graph will be 3-regular. It's easy to make degree-2 vertices without changing the degree of any other vertex: just take an existing edge and put a new vertex in the middle of it. (This is known as "subdividing".)

So, the recipe is this:

1. Take three disjoint 3-regular graphs (e.g., three copies of $K_4$) plus one new central vertex.
2. For each of the graphs, pick an edge and add a new vertex in the middle of it.
3. Add edges from each of these three vertices to the central vertex.