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

  • $\begingroup$ 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... $\endgroup$ – JMoravitz Feb 27 '17 at 17:52
  • 1
    $\begingroup$ Your mistake is the claim "A cut vertex cannot belong to a cycle" $\endgroup$ – JMoravitz Feb 27 '17 at 17:53
  • $\begingroup$ Ah, you are right! I mixed it up with a cut-edge! $\endgroup$ – Anshul Feb 27 '17 at 17:57

Here is a counterexample:

    |   |

Note that the four middle vertices are cut vertices even though they lie on a cycle.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.