Proving Cut Vertices in Simple Graphs

[mooncrater]

Homework Statement

The given question is:
Show that a simple graph with at least two vertices has at least two vertices that are not cut vertices.

Homework Equations

Cut vertices: The removal of cut vertices and all edges incident to them produces a subgraph more connected components than in the original graph.

The Attempt at a Solution

What I did:
Assuming a $S$ represents that a graph is simple, and $x$ is the number of cut vertices in it. So we have to prove $$S→x>=2$$. We can also prove it through contradiction by proving the negation of the above statement to be always false( that is, a contradiction). So, we can write $S→x>=2$ as
~S√(x>=2) (where √ represents a disjunction)
Whose negation is
S^(x<2).
So, if we prove that having a simple graph having all vertices as cut-vertices or just one non-cut vertex is a contradiction, then does that prove our original statement? Do we still have to prove that 2 non-cut vertices are necessary?
Thanks
Moon

 

[andrewkirk]

Assuming a $S$ represents that a graph is simple, and $x$ is the number of cut vertices in it. So we have to prove $$S→x>=2$$.

No, that's not what is being asked. They are asking you to prove that, if $n(S)\geq 2$,. where $n(S)$ is the number of vertices in $S$, we have:

$$n(S)-x(S)\geq 2$$

However, the answer to this:

So, if we prove that having a simple graph having all vertices as cut-vertices or just one non-cut vertex is a contradiction, then does that prove our original statement?

is Yes, and hence the answer to this

Do we still have to prove that 2 non-cut vertices are necessary?

is No.

You are asked to prove that $n(S)-x(S)\geq 2$, which is equivalent to proving that $x(S)\leq n(S)-2$ which, since $x(S)\leq n(S)$, is equivalent to proving that
$$x(S)\neq n(S)\wedge x(S)\neq n(S)-1$$

 

[mooncrater]

Thanks! I got it now.☺
Moon.