Handshake Lemma/Examples
Jump to navigation
Jump to search
Examples of Use of Handshake Lemma
Arbitrary Order $8$ Graph
The above simple graph has $8$ vertices and $10$ edges (which can be ascertained by counting).
\(\ds \map \deg {v_1}\) | \(=\) | \(\ds 2\) | ||||||||||||
\(\ds \map \deg {v_2}\) | \(=\) | \(\ds 3\) | ||||||||||||
\(\ds \map \deg {v_3}\) | \(=\) | \(\ds 3\) | ||||||||||||
\(\ds \map \deg {v_4}\) | \(=\) | \(\ds 3\) | ||||||||||||
\(\ds \map \deg {v_5}\) | \(=\) | \(\ds 4\) | ||||||||||||
\(\ds \map \deg {v_6}\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \map \deg {v_7}\) | \(=\) | \(\ds 2\) | ||||||||||||
\(\ds \map \deg {v_8}\) | \(=\) | \(\ds 2\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum \map \deg V\) | \(=\) | \(\ds 2 + 3 + 3 + 3 + 4 + 1 + 2 + 2\) | |||||||||||
\(\ds \) | \(=\) | \(\ds 20\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 2 \times 10\) |
Impossible Order $6$ Graph
There exists no undirected graph whose vertices have degrees $2, 3, 3, 4, 4, 5$.
No Graph with One Odd Vertex
There exists no undirected graph with exactly one odd vertex.