4.23 Euler Walking

Handshaking lemma
Subgraph(Induced subgraph)
Trees
Connected (Any two vertices have a walk connecting them)
Acyclic (don't have cycles or subgraph isomorphic to cycle graphs)
Every tree has a leaf (\(\deg=1\) vertex)
Every tree on \(n\geq 1\) vertices has \(n-1\) edges

Spanning subgraph

Let \(\Gamma=(V,E)\) is a subgraph of \(\Gamma'=(V',E')\) we say that \(\Gamma\) is a spanning subgraph if \(V=V'\)

Every graph with \(e\) edges has \(2^e\) spanning subgraphs

Proposition

Every connected graph has a spanning tree, that is, a spanning subgraph is isomorphic to a tree

Illustration:

Proof

Let \(\Gamma=(V,E)\) be a connected graph and \(T\) be an acyclic spanning subgraph of \(\Gamma\) with maximal possible numbers of edges (the set of acyclic spanning subgraphs is non-empty since the empty graph are in the set)

If \(T\) is a tree, we are done. If not, then \(\exists u,v\in V:\) don't admit a uv-walk inside \(T\)

Consider \(P\) is a shortest uv-path inside \(\Gamma\), then \(P\) has an edge \(e=(x,y)\) such that there are no walk in \(T\) connecting \(x\) and \(y\)

Then adding \(e\) to \(T\), then claim: \(T\) with \(e\) added to it is still acyclic.

Because otherwise, we should have had two different paths inside \(T\cup\{e\}\) connecting \(x,y\) since every cyclic has two paths connecting \(x,y\), which is contradiction to our construction

So the original \(T\) doesn't have maximum possible number of edges

Corollary

A connected graph on \(n\) vertices and \(n-1\) edges is a tree

Proof

This graph should have a spanning tree. This tree has \(n-1\) edges. So all the edges of the original graph are there, so the original graph is a tree

Counting the number of labelled trees on \(n\) vertices

Cayley's formula(Borchardt)

The number of labelled trees on \(n\) vertices equals \(n^{n-2}\)

Prüfer codes

A Prüfer code of index \(n\) is a sequence of \(n-2\) elements of the set \(\{1,...,n\}\)

E.g.: 4445 \(\leftarrow\) Prüfer code of index 6

Theorem

Let \(n\geq 2\), then there is a bijection between the set of labelled trees on \(n\) vertices and Prüfer codes of index \(n\)

Proof

Tree \(\rightarrow\) code

Trees on \(n\geq 2\) vertices have leaves

Step: Take the leaf with the smallest label, delete it and write the label of the adjacent vertex into the code. Do until only two vertices left.

Example: For the tree:, we have

Another example:

Observation: the number of times a label appears in the code equals \(\deg i-1\)

Code \(\rightarrow\) Tree

Make a list of labels, together with the expected degrees

Example: 3111, then write the list: 1⁴ 2¹ 3² 4¹ 5¹ 6¹

Euler's walks and Euler's tours

Now, the graphs we study are allowed to have serval edges connecting vertices \(v\) and \(u\)

And also are allowed to have loops: edges that connect a vertex to itself

E.g.:

Leonhard Euler

Is it possible to make a walk such that it crosses every bridge exactly one?

Definition

Let \(\Gamma\) be a connected graph (multiedges and loops are allowed).

An Euler's walk in \(\Gamma\) is a walk such that every edges of the graph used exactly once

An Euler's tour is a Euler's walk such that starts and ends in the same vertex

Theorem

A connected graph \(\Gamma\) admits an Euler's tour if the degree of every its vertex is even

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

‍