Graph Proof

  • Thread starter mooncrater
  • Start date
  • #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:

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,886
1,454
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$$
 
  • Like
Likes mooncrater
  • #3
217
18
Thanks! I got it now.☺
Moon.
 

Related Threads on Graph Proof

  • Last Post
Replies
0
Views
859
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
542
  • Last Post
Replies
3
Views
663
  • Last Post
Replies
21
Views
6K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
11
Views
2K
Top