1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Proof

  1. Jun 17, 2016 #1
    1. The problem statement, all variables and given/known data
    The given question is:
    Show that a simple graph with at least two vertices has at least two vertices that are not cut vertices.


    2. Relevant 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.


    3. 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: Jun 18, 2016
  2. jcsd
  3. Jun 17, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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:
    is Yes, and hence the answer to this
    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$$
     
  4. Jun 18, 2016 #3
    Thanks! I got it now.☺
    Moon.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Graph Proof
  1. Graph Proof (Replies: 0)

  2. Graph Theory Proof (Replies: 3)

  3. Graph theory proof (Replies: 3)

Loading...