Handshake Lemma/Examples

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.