1
$\begingroup$

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

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

1 Answer 1

Reset to default
3
$\begingroup$

Here is a counterexample:

O---O---O---O
    |   |
O---O---O---O

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .