Results 1 to 5 of 5

Math Help - Graph Theory with Prooving

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    33

    Graph Theory with Prooving

    Let F be a Simple Graph with n >=2 vertices.
    Proove that F contains at least two vertices of the same degree.


    well i know that A graph is called simple if there is at most one edge between any two points.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by AwesomeDesiKid View Post
    Let F be a Simple Graph with n >=2 vertices.
    Proove that F contains at least two vertices of the same degree.


    well i know that A graph is called simple if there is at most one edge between any two points.
    let d_i be the degree of the vertex v_i. then either d_i \in \{1, 2, \cdots , n-1 \}, \ \forall i, or d_i \in \{0,1, \cdots, n-2 \}, \ \forall i. you should be able to easily finish the proof now.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by NonCommAlg View Post
    let d_i be the degree of the vertex v_i. then either d_i \in \{1, 2, \cdots , n-1 \}, \ \forall i, or d_i \in \{0,1, \cdots, n-2 \}, \ \forall i. you should be able to easily finish the proof now.
    thank you for this...just little bit more
    well i see that you are making two sets and one less then other, but how are you supposed to put that in to proof language...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by AwesomeDesiKid View Post
    thank you for this...just little bit more
    well i see that you are making two sets and one less then other, but how are you supposed to put that in to proof language...
    the number of elements of both sets is n-1. so we have n vertices and n-1 possible values for the degrees of the vertices. thus at least two vertices must have the same degree.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by NonCommAlg View Post
    the number of elements of both sets is n-1. so we have n vertices and n-1 possible values for the degrees of the vertices. thus at least two vertices must have the same degree.
    thank you
    you are a life saver
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 06:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM

Search Tags


/mathhelpforum @mathhelpforum