티스토리 뷰

Prove that for .


Intuition: 

Suppose n people shake hands with other people in the group.  They don't shake hands twice with the same person.

How many handshakes take place?

각 사람을 노드로 본다면 두 사람이 악수를 하면 그 두 노드 사이에 Edge 가 생긴다.

전체 악수의 수 = Number of Edges in the graph  = 각 사람이 한 악수의 수의 총합 / 2 

                         = Sum of degree of every vertex / 2


Let be the vertices of G and their degrees respectively. Also, 



Then we know that





Corollary : Every graph has an even number of vertices with odd degree.


Since is surely an integer,


must be an integer.


Then must be an even number.


We want to show that an even number of the above terms are odd numbers.


The remaining numbers in the sum above are even numbers, which always add up to an even number regardless of how many of them there are.


Since the sum is even, subtracting the partial sum of even numbers which is an even number, the odd numbers have to add up to become an even number.


The only possible way is for there to be an even number of odd numbers. QED



댓글
댓글쓰기 폼