Skip to content

4.28 Euler Tour and The Pigeonhole principle

Theorem(Euler)

A connected graph \(\Gamma\) admits an Euler's tour iff all vertices of \(\Gamma\) are of even degree

A connected graph \(\Gamma\) is an Euler's walk which is not an Euler's tour iff there are exactly 2 vertices of odd degree

image​

Proof

\(\Rightarrow\)) If a graph has an Euler's tour, every its vertex should have the same number of entries and exits

This requires all the vertices to have even degress.

If a graph has an Euler's walk that is not a tour, there is a starting vertex and an ending vertex of the walk. They should have odd degrees

\(\Leftarrow\)) Suppose we have a connected graph \(\Gamma\) with exactly two vertices of odd degree.

Denote them by \(u\) and \(v\)

  1. Start at \(u\), keep doing the following, check all the edges incident to the vertex you are in at the moment

    There are any we haven't visited so far

    If yes, make the next step

    If no, terminate

    Illustration:image​

    Fixed the constructed walk: \(u\overset{e_0}{\rightarrow}w_1\overset{e_1}{\rightarrow}w_2\rightarrow...\rightarrow w_k\overset{e_{k+1}}{\rightarrow}v\)​

    If this walk is Euler, we are done.

    If not, erase all the edges we visited. All the degrees in the resulting graph are even

    image​

    Notice that in the resulting graph there is at least one edge incident to a vertex we have visited

    Why

    Suppose there are no unvisited edges incident to all the vertices we visited of the graph

    1. If the vertices we visited are all the vertices of the graph, then we have visited all the edges
    2. If there are vertices we haven't visited, it's impossible to have are no unvisited edges incident to the vertices we visited\

    image​

  2. Start in the vertex \(w_i\), keep walking along non erased edges of the graph making sure that you never visit the same edge twice until it's possible

    image​

    Extend the walk we constructed: \(\overset{e_{i-1}}{\rightarrow}w_{i}\overset{e_{i}}{\rightarrow}\mapsto\overset{e_{i-1}} {\rightarrow}w_{i}\overset{e_{0}}{\rightarrow}w_0\overset{e_{1}}{\rightarrow}...\overset{e_{k'}}{\rightarrow}w_i\overset{e_{i}}{\rightarrow}\)

    Repeat: erase all the edges we have visited and check if there are any edges left

    image​

Corollary

Notices that it is always possible to add some more edges to a graph \(\Gamma\) to make it have an Euler's tour

Proof

By Handshaking lemma, \(\sum_v\deg v=2|E|\) in any graph the number of vertices of odd degree is even

The Ramsey theory and the Pigeonhole principle

Suppose there was a party with 6 participants. Every two of them either knew each other before the party or didn't know each other before the party

Show that there was either 3 person that knew each other or there was 3 person that didn't know each other

image​

Suppose \(\Gamma\) is a graph. A p-clique in \(\Gamma\) is an induced subgraph isomorphic to a complete graph on p vertices

A q-anticlique in \(\Gamma\) is an induced subgraph isomorphic to an empty graph on q vertices

Equivalent formulation

Prove that any graph on 6 vertices either has a 3-clique or a 3-anticlique

Notice that there are graphs on 5 vertices that neither have 3-cliques nor 3-anticliques

image​

Proof

Pick vertex 1, study its relation to the remaining vertices

Consider \(f:\{2,3,4,5,6\}\to\left\lbrace⚫⚪\right\rbrace\) where \(i\mapsto \begin{cases} ⚪,1_{i}\text{ is not an edge} \\ ⚫,1_{i}\text{ is an edge} \end{cases}\)

image​

\(\#f^{-1}\left(⚪\right)+\#f^{-1}\left(⚫\right)=5\). Either \(\#f^{-1}\left(⚪\right)\) or \(\#f^{-1}\left(⚫\right)\) is at least 3

Suppose not, contradiction

Suppose \(\#f^{-1}\left(⚪\right)\geq 3\). Choose some three of its preimages

If all them are pairwise connected, we have a 3-clique

Suppose some 2 of them are not connected, then these two plus 1 form a new 3-anticlique

The case \(\#f^{-1}\left(⚫\right)\geq 3\) is treated similarly

image​

On the way of proving this statement we have used one of the versious of so-called Pigeonhole Principle (Dirichlet's drawer principle)

  • Basic version: Suppose we have \(n\) cages and \(n+1\) pigeons. Whatever way to distribute pigeons into cages we use, there should be at least one cage that has at least 2 pigeons
  • A bit stronger version:

Let \(\#A\geq kr+1,\#B= r\) where \(k,r\in \N\). Then there exists \(b\in B\) such that \(\#f^{-1}(b)\geq k+1\) (we have used this for \(k=2,r=2\) above)

Proof

Suppose \(\forall b\in B,\#f^{-1}(b)\leq k\), then \(\#A=\sum_{b\in B}\#f^{-1}(b)\leq kr\), contradiction * The strongest version

Let \(q_1,...,q_m\in \N\), \(A\) is a set with \(q_1+q_2+...+q_m-m+1\) elements. \(B\) is a set with \(m\) elements such that \(B=\{1,2,...,m\}\)​

Then \(\exists i\in B\) s.t. \(\#f^{-1}(i)\geq q_i\)​

Proof

Suppose \(\forall i=1,\ldots,m,\#f^{-1}(i)<q_i\), then \(\sum^m_{i=1}f^{-1}(i)\leq (q_1-1)+(q_2-1)+...+(q_m-1)=q_1+...+q_m-m\) which is a contradiction