Let F be aSimple Graphwith n $\displaystyle >=$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.

Printable View

- Dec 7th 2009, 08:32 PMAwesomeDesiKidGraph Theory with Prooving
Let F be a

__Simple Graph__with n $\displaystyle >=$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. - Dec 7th 2009, 10:12 PMNonCommAlg
let $\displaystyle d_i$ be the degree of the vertex $\displaystyle v_i.$ then either $\displaystyle d_i \in \{1, 2, \cdots , n-1 \}, \ \forall i,$ or $\displaystyle d_i \in \{0,1, \cdots, n-2 \}, \ \forall i.$ you should be able to easily finish the proof now.

- Dec 7th 2009, 10:21 PMAwesomeDesiKid
- Dec 7th 2009, 10:34 PMNonCommAlg
- Dec 7th 2009, 10:36 PMAwesomeDesiKid