# Math Help - Graph Theory with Prooving

1. ## 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.

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

3. 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...

4. 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.

5. 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