# Graph Theory with Prooving

• December 7th 2009, 09:32 PM
AwesomeDesiKid
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.
• December 7th 2009, 11:12 PM
NonCommAlg
Quote:

Originally Posted by AwesomeDesiKid
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.
• December 7th 2009, 11:21 PM
AwesomeDesiKid
Quote:

Originally Posted by NonCommAlg
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...
• December 7th 2009, 11:34 PM
NonCommAlg
Quote:

Originally Posted by AwesomeDesiKid
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.
• December 7th 2009, 11:36 PM
AwesomeDesiKid
Quote:

Originally Posted by NonCommAlg
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(Handshake)