Graph Theory: Euler, hamilton

Heyy! Welcome Back to my blog!

 Today we are doing Graph Theory. This post is a continuation of a previous post which if you are interested in here. I somehow always get scared when someone mentions Graph theory. I have to overcome the fear. So here we go! I am writing some important theorems, terms, problems, etc that I learnt from the GT books! In short, notes.

Book referred: Daniel A Marcus, Graph Theory, A Problem Oriented Approach

Chapter F:

• Euler Path: An Euler path in a graph $G$ is a path that includes every edge of $G$ exactly once. ( Not all graphs have Euler Paths)
• Closed Euler Path: An Euler path is closed if it starts and ends at the same vertex.
  
• Open Euler Path: Not closed.

Problem 1: Show that if a graph has at least one edge, and if all vertices have an even degree, then the graph must contain at least one cycle.
Proof: Suppose, it doesn't. Then consider a component of the graph $G.$ Then the component is a tree ( since it has no cycles). But we know a tree has at least $2$ nodes, which have an odd degree.

Problem 2: If a graph contains an Euler path, then it has $0$ or $2$ odd vertices.
Proof: Suppose there are more than $2$ odd vertices, then there is a vertex $A$ which is not the endpoints of the Euler path ( if it's not closed). Now, each time one visits $A,$ we will have to travel in and then out, in order to go to the next vertex.  Implying $A$ must be an even degree.

Problem 3: If a graph contains an Euler path and has $2$ odd vertices implies that the Euler path is open.
Proof: By the above problem, we get that "Non-end points" must-have degree even. So the two odd vertices must be endpoints of the euler path $\implies$ Euler path is open.

The Euler Path Theorem: 

1. A graph or multigraph contains a closed Euler path iff 

a. Every vertex has an even degree
b. All edges are in the component.

2.  A graph or multigraph contains an open Euler path iff 

a. Every vertex has an odd degree
b. All edges are in the component.

Proof: 
1. We know that the graph $G$ will contain a cycle $C.$ Now delete the cycle $C.$ Note that the new graph $G'$ will still have even degree vertices. And we will have a new cycle. Delete it and so on. Repeat the process. Note that this will continue till our graph becomes a cycle.

Now, we merge all these cycles. 
Say we have a cycle, $V_1\rightarrow V_2\rightarrow \dots \rightarrow V_k\rightarrow$ and we have another cycle, $V_i\rightarrow D_1\rightarrow \dots \rightarrow D_k\rightarrow V_i.$

Then consider this path, 
$$V_1\rightarrow V_2\rightarrow \dots V_{i-1}\rightarrow V_i\rightarrow D_1\rightarrow \dots \rightarrow D_k\rightarrow V_i\rightarrow \dots V_k$$

And we can repeat this process.

2. Let the two odd vertices be $A$ and $B.$ And the number of edges to be greater than $1.$ So $A$ and $B$ are not adjacent. Then join $AB.$ By part 1, we know there is a closed Euler path. So removing $AB$ we get an open Euler path.

The Euler Path Theorem directed version: 

1. A graph or multigraph contains a closed Euler path iff 

a. At each vertex, the in degrees $=$ out-degree 
b. All edges are in the component.

2.  A graph or multigraph contains an open Euler path iff 

a. At one vertex, in degree $-$ out degree $=1,$ at one vertex, out degree $-$ indegree$= 1,$ rest vertex have indegree$=$outdegree.
b. All edges are in the component.

Chapter G:

• Hamilton Path: A hamilton path in a graph $G$ is a simple path that contains every vertex of $G.$
• Hamilton Cycle: A cycle containing every vertex of $G.$

Problem 1: Suppose $G$ is a bipartite graph with $m$ vertices of one colour and $n$ vertices of the other colour. If $m\ne n,$ $G$ contains no hamilton cycle.

Proof: Let $X=\{v_1,\dots,v_m\},Y=\{d_1,\dots,d_n\}$ be the vertices. If hamilton cycle is being formed, the cycle would be of the form $(v_{i_1},d_{j_1},v_{i_2},\dots d_{j_x},v_{i_1}).$ Note that vertices of different colour are alternating, since all vertices are included once only, we get $m=n.$

Problem 2:  Suppose $G$ is a bipartite graph with $m$ vertices of one colour and $n$ vertices of the other colour. If $m-n\ge 2$ $G$ contains no hamilton cycle.

Proof: Similar proof, but we get $\max(m-n)=1.$

Using the above two problems, we get the following.

 $K_{m,n}$ contains a hamilton cycle iff $m=n.$

Problem 3: If $k$ vertices are removed from a graph that contains a hamilton path, then the number of components in the resulting subgraph is at most $k+1.$

Proof: Before removing the $k$ vertices, note that the graph was connected. Let $(d_1,d_2,\dots d_n)$ be the hamilton path. We remove $v_1,\dots,v_k.$ Then the hamilton path divides into $k+1$ parts. Consider $(d_1,\dots, d_i)$ such that $d_i$ was just before $v_1.$ Then the subgraph $(d_1,\dots, d_i)$ is connected. Similarly for the other subgraphs. Hence the number of components in the resulting subgraph is at most $k+1.$

Problem 4: If $k$ vertices are removed from a graph that contains a hamilton cycle, then the number of components in the resulting subgraph is at most $k.$

Proof: The proof is similar to the above. But then since it's a cycle, after removing we get $k$ parts.



Following are some fancy results that help us prove that the Hamilton cycle will exist. 

The path cyle principle:

Let $G$ be a graph with $n$ vertices, where $n\ge3,$ suppose that $G$ contains a hamilton path whose endpoints ( $A$ and $B$) satisfy the condition $d(A)+d(b)\ge n.$

Proof: Let the hamilton path be $(A,v_1,v_2,\dots,v_{n-2},B).$ 
If $A$ and $B$ are adjacent then we are done, so let's assume $A$ and $B$ are not adjacent. 
We try to get something of this form.

We want to get edges $Av_{i+1}$ and $Bv_i$ to exist in graph $G.$ And then we can consider the hamilton cycle $(v_{i+1},A,v_1,v_2\dots, v_i, B, v_{n-2},\dots, v_{i+1}).$

Now consider the set $S$ be the set of $i$ such $Av_{i+1}$ are adjacent and $1\le i\le n-3.$

And consider the set $T$ be the set of $i$ such $Bv_{i}$ are adjacent and $1\le i\le n-3.$

Then note that $|S|=d(A)-1,|T|=d(B)-1.$ And $d(a)+d(b)-2\ge n-2.$ So $S\cap T\ge 1.$

The Bondy-Chvatal Theorem: 

Let $G$ be a graph with $n$ vertices, where $n\ge 3$ and suppose that $G$ can be expanded to a larger graph $G'$ that contains a hamilton cycle, by adding edges once at a time in such a way that the following condition is satisfied.

The bondy-chvatal condition: An edge can be added joining vertices $A$ and $B$ if $A$ and $B$ are not already adjacent and if their degrees satisfy $d(A)+d(B)\ge n.$

Proof: Suppose $G$ does not contain any hamilton cycle but $G'$ is. Then there will be a stage when $G_k$ does not contain a hamilton cycle but $G_{k+1}$ does. Say edge we add while converting $G_k$ to $G_{k+1}$ is $CD.$ Then we have $CD$ part of the hamilton cycle, hence we have a hamilton path in $G_k$ with $CD$ endpoints. But we also have $d(C)+d(D)\ge n\implies$ hamilton cycle exist in $G_k$ by path cycle principle.


Ore's theorem:

Let $G$ be a graph with $n$ vertices, where $n\ge 3$ and suppose that $G$ satisfies 
Ore's adjacency condition Whenever $d(A)+d(B)<n$ for two vertices $A$ and $B,$ $A$ and $B$ are adjacent.
Then $G$ contains a hamilton cycle.

Proof: Consider two vertices  ( say $C$ and $D$) which are not adjacent in $G.$ Then we must have $d(C )+d(D)\ge n.$ And we can continue this process and get $K_n.$ But $K_n$ contains  hamilton cycle, so by bondy-chvatal theorem, we are done.

Dirac's theorem can be skipped since Posa's theorem is a stronger version anyways.

Dirac's theorem: 

Let $G$ be a graph with $n$ vertices, where $n\ge 3,$ and suppose that each vertex greater than or equal to $n/2.$ Then $G$ contains a hamilton cycle.

Proof: Note that we can join any two vertices as any two vertice degree sum is greater than n-1. Then at the end, we get a $K_n.$  But $K_n$ contains  hamilton cycle, so by bondy-chvatal theorem, we are done.

Posa's theorem: 
Let $G$ be a graph with $n$ vertices, where $n\ge 3$ and $d_1\le d_2\le \dots \le d_n$ be the degrees satisfy the condition

Posa's degree condition: $d_1>1,d_2>2,\dots d_i>i$ for all $i<n/2.$

Proof: We will try to complete the graph by joining to non adjacent vertices $A$ and $B$ with $d(A)+d(B)\ge n$ and we will eventually get $K_n.$ And we will be done by bondy-chvatal theorem.

If $d_1+d_2\ge n$ we are done, so let's assume $d_1+d_2<n.$
Note that $d_r+d_{r+1}\ge n$ for $r=[n/2].$

So there must be $2\le i\le r$ such that $$d_{i-1}+d_i< n, ~~ d_i+d_{i+1}\ge n.$$ So $d_i<n-i.$

Now let $A$ be the vertex having degree $d_i.$ Now consider the $n-i$ vertices which have degree $d_{i+1},d_{i+2},\dots, d_{n}.$ 

Since $d_i<n-1\implies$ there is a vertex which have degree $\ge d_{i+1}$ and is not adjacent to $A.$ We let that vertex be $B$ and join them. We are done.

 

Phew! That was a lot for me. I will post the sequel tomorrow!

Sunaina 💜