- #1

- 217

- 18

## 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

Last edited by a moderator: