1. Not finding help here? Sign up for a free 30min 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 theory proof help

  1. Nov 5, 2009 #1
    1. The problem statement, all variables and given/known data

    Let G be a graph with at least two vertices, such that the cut induced by every
    proper nonempty subset of vertices of G contains exactly two elements. Determine
    (with proof ) the number of vertices and edges in G.

    2. Relevant equations

    Connectedness. A graph G is connected if for any two vertices x and y in G, there is a path from x to y.

    3. The attempt at a solution
    I'm really stuck. But i think proving by contradiction is a good approach (maybe??).
    i.e.: Suppose the graph is not connected...i.e. it has more than one component. ......?????
    this is a contradiction...therefore the graph is connected?
    like i said. i'm really having troubles. any help would be greatly appreciated.
    thanks in advance.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Nov 5, 2009 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What do you mean by the cut induced...? I don't remember hearing that specific usage of the word cut regarding graph theory but I may have just forgotten
     
  4. Nov 5, 2009 #3
    Given a subset X of the vertices of G, the cut induced by X is the set of edges that have exactly one end in X.

    Maybe the theorem: A graph G is not connected if and only if there exists a proper nonempty subset X of V(G) such that the cut induced by X is empty helps?
     
  5. Nov 5, 2009 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ok, so you're given a graph G. For any subset of G, say X, there are exactly two edges going from X to G-X

    Start by picking a single vertex in G and notice that if X is a single vertex, that vertex has to have degree 2. What are your possible choices for G? Then by picking other subsets X narrow it down further
     
  6. Nov 6, 2009 #5
    still lost. if i pick 2 vertices...?????? 3 vertices???
     
  7. Nov 6, 2009 #6

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    It will help if you write down exactly what the set of all possible connected graphs are for which every vertex has degree 2
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Graph theory proof help
  1. Graph Theory Proof (Replies: 3)

Loading...