Week 2 > Handshaking Lemma Flashcards
1
Q
A
2
Q
What is Handshaking Lemma?
A
3
Q
We know that the number of odd points is always even. Are there 9 points of degree 5?
A
No, it should be degree = 5 (odd) -> 10 points
4
Q
Can you present an odd number of people having odd number of handshakes is even using
graphs?
A
In graph terms: A graph has an even number of nodes
5
Q
What is the lemma of the degree sum formula?
A
6
Q
What is the implication of the degree sum formula on the handshake lemma?
A
7
Q
Doe the degree sum formula stands true for the handshake lemma (provide proof)?
A
- Remove all edges
- No adding them back, one by one
8
Q
Can you provide the summary of applying induction to Handshake Lemma using the degree sum formula?
A
9
Q
A
10
Q
Draw graph solution of exam problem
A
11
Q
- Why exam graph is bipartite?
- What technique was used to solve the problem?
A
