## 티스토리 뷰

Comp Sci/Algorithms

### The Handshake Theorem and Its Corollary

jeongtaebang 2017.12.21 22:06

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

#### 'Comp Sci > Algorithms' 카테고리의 다른 글

 [Math] Permutations, Combinations, and Multiplication  (0) 2018.06.19 2017.12.23 2017.12.22 2017.12.21 2017.11.28 2017.11.26
공유하기 링크
TAG
, , ,
댓글
댓글쓰기 폼
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
1,079
Today
0
Yesterday
0
링크
TAG more
«   2019/07   »
1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31
글 보관함