Math 240 Discrete Mathematics - Handshaking Lemma

Handshaking Lemma

The first graph theory problem

$G=(V,E)$

In any graph, there are an even number of points (vertices) that touch an odd number of lines (edges).

Definition

Given a graph $G=(V,E)$ and $v\in V$, the degree of $v$ is the number of edges that contain $v$, and is denoted $d(v)$ or $d_G(v)$

For example

.. figure:: |filename|/math240res/images/handshakinglemmaexample.png

Lemma: Handshaking Lemma

For any graph $G=(V,E)$.

\[ \sum_{v \in V} d(v) = 2|E| \]

This immediately implies the fact from last class.

Proof: Each edge is counted twice in total, once by each of its endpoints.

Walk

A walk in a graph $G=(V,E)$ is just a sequence of vertices, $w_1,w_2,\dots,w_{k-1},w_k$ such that $\{w_1,w_2\} \in E$, $\{w_2,w_3\} \in E$, … $\{w_{k-1},w_k\} \in E$

Example: ababcecd is a walk

A walk is a path if it has no repeated vertices. A graph $G=(V,E)$ is connected if for any $u,v \in V$, there is a walk starting at u, ending at v.

Fact

if there is a walk from u to v then there is a path from u to v.

Proof

Let $u=w_1,w_2,\dots,w_k=v$ be a walk from u to v of minimum length. If $w_1,w_2,\dots,w_k$ is not a path, then there is some $i<j$, such that $w_i=w_j$, and then $w_1,w_2,\dots,w_i,w_j,\dots,w_k$ is a shorter walk, then $w_1,w_2,\dots,w_k$ is a path.

Circuit, Cycle and Eulerian

A circuit is a walk $w_1,w_2,\dots,w_k$ sucht that $w_k = w_1$. The circuit is a cycle if $w_1,w_2,\dots, w_k-1$ is a path.

An Eulerian walk in $G=(V,E)$ is a walk that uses each edge exactly once. An eulerian circuit is a circuit that uses each edge exactly once.

A graph is Eulerian if it has an Eulerian circuit.

Theorem (Euler, 1736)

If $G$ is a (connected) graph, then it is Eulerian if and only if all vertex degrees are even.

Proof

“$\rightarrow$” Suppose $G$ has an Eulerian circuit $w_1,w_2,\dots,w_k$, Fix any vertex $v \in V$. Then $v$ appears at some points in the walk, say $w_{i_1},w_{i_2},\dots, w_{i_j}$.

If $i_1 \not = 1$: Then the edges of $G$ incident to $c$ are

\[ \left\{ w_{i_1-1},v \right\}, \left\{ v,w_{i_1+1} \right\}, \left\{ w_{i_2-1},v \right\}, \left\{ v,w_{i_2+1} \right\},\dots, \left\{ w_{i_j-1},v \right\} , \left\{ v,w_{i_j+1} \right\} \]

So $d_G(v) =2_j$

If $i_1 = 1$: Then $d_G(v)=2(j-2)+1+1 = 2(j-1)$