# Is a connected graph in which every vertex with degree at least two being a cut vertex necessarily a tree?

The question is framed as:

Let G be a connected graph in which every vertex of degree at least two is a cut vertex. Is it true that G must be a tree?

I claim that it is so and the outline of my proof is as follows. Also note that my instructor does not agree (and I am still not sure if it is my method that is not agreeable or is the claim wrong). Please help:

We proceed by Contradiction: Let G be a connected graph with every Vertex with degree at least 2 as a cut vertex and let it NOT be a tree. Then, it either contains cycles or is a forest. It can't be a forest since it is connected, so it must contain cycles. Remove a cut-vertex from the graph. This divides the graph G into 2 components (by definition of Cut Vertex). But, minimum degree in a cycle is also 2, and if above claim is true, each vertex in the cycle is a cut-vertex. But a cut vertex cannot belong to a cycle and this is a contradiction.

Thus, a connected graph with above mentioned properties must necessarily be a tree.

So, what is the problem with this proof? (Is it really a proof?)

(While writing this, I realized that I could just state that "Any vertex is cut vertex if it does not lie on a cycle. Any vertex in a cycle must have minimum degree 2. Since the graph is connected and each vertex with degree at least 2 is a cut vertex, it is a tree.)

• I'm imagining a picture of a cartoonish sun drawn like a circle with little wavy lines coming off of it... I wonder if I were to draw a graph like that if it would satisfy the hypothesis... Feb 27, 2017 at 17:52
• Your mistake is the claim "A cut vertex cannot belong to a cycle" Feb 27, 2017 at 17:53
• Ah, you are right! I mixed it up with a cut-edge! Feb 27, 2017 at 17:57

O---O---O---O