Prove that for , .
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
'Comp Sci > Algorithms' 카테고리의 다른 글
|Proof - Euler Trail Theorem (2) (0)||2017.12.23|
|Proof - Euler Trail Theorem (1) (1)||2017.12.22|
|The Handshake Theorem and Its Corollary (0)||2017.12.21|
|Loop Invariant Practice - Merge() of MergeSort() (0)||2017.11.28|
|Java Implementation of Karatsuba's Algorithm (카라츠바 곱셈 알고리즘 구현) (0)||2017.11.26|
- Proof of Correctness
- Two Pointer