Skip to main content

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 💜



Labels:

Comments

  1. AnandDecember 24, 2021 at 9:38 AM

    Woah a lot of new stuff up there; nice post!

    PS: iirc Ore's theorem made it's appearance in INMO 21

    ReplyDelete
    Replies
    1. Sunaina Pati December 24, 2021 at 11:05 AM

      Hi Anand, long time no talk :pleading:.. Thanks a lot for commenting! And yes, I heard people mentioning Ore's theorem in INMO 21 was equivalent to 10+ marks... :O

      Delete

Post a Comment

Popular posts from this blog

My experiences at EGMO, IMOTC and PROMYS experience

Yes, I know. This post should have been posted like 2 months ago. Okay okay, sorry. But yeah, I was just waiting for everything to be over and I was lazy. ( sorry ) You know, the transitioning period from high school to college is very weird. I will join CMI( Chennai Mathematical  Institue) for bsc maths and cs degree. And I am very scared. Like very very scared. No, not about making new friends and all. I don't care about that part because I know a decent amount of CMI people already.  What I am scared of is whether I will be able to handle the coursework and get good grades T_T Anyways, here's my EGMO PDC, EGMO, IMOTC and PROMYS experience. Yes, a lot of stuff. My EGMO experience is a lot and I wrote a lot of details, IMOTC and PROMYS is just a few paras. Oh to those, who don't know me or are reading for the first time. I am Sunaina Pati. I was IND2 at EGMO 2023 which was held in Slovenia. I was also invited to the IMOTC or International Mathematical Olympiad Training Cam...
11 comments
Read more

Orders and Primitive roots

 Theory  We know what Fermat's little theorem states. If $p$ is a prime number, then for any integer $a$, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as \[a^{p}\equiv a{\pmod {p}}.\] So, essentially, for every $(a,m)=1$, ${a}^{\phi (m)}\equiv 1 \pmod {m}$. But $\phi (m)$ isn't necessarily the smallest exponent. For example, we know $4^{12}\equiv 1\mod 13$ but so is $4^6$. So, we care about the "smallest" exponent $d$ such that $a^d\equiv 1\mod m$ given $(a,m)=1$.  Orders Given a prime $p$, the order of an integer $a$ modulo $p$, $p\nmid a$, is the smallest positive integer $d$, such that $a^d \equiv 1 \pmod p$. This is denoted $\text{ord}_p(a) = d$. If $p$ is a primes and $p\nmid a$, let $d$ be order of $a$ mod $p$. Then $a^n\equiv 1\pmod p\implies d|n$. Let $n=pd+r, r\ll d$. Which implies $a^r\equiv 1\pmod p.$ But $d$ is the smallest natural number. So $r=0$. So $d|n$. Show that $n$ divid...
7 comments
Read more

IMO Shortlist 2022 C1

  Today we shall try IMO Shortlist $2022$ C1. A $\pm 1$-sequence is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and$$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.$$ We claim that the answer is $\boxed{506}$. $506$ is the upper bound. Just consider the sequence $$+1,-1,-1,+1,+1,-1,-1,+1\dots,-1,-1,+1,+1,-1.$$ Here $1, -1, -1, 1$ is repeated $505$ times and $1,-1$ is concatted to it. Now,our sequence would be $a_1,a_3,a_4,a_5,a_7,\dots$ which on summing would give $506$. And clearly, this would give the upper bound. Now, we show that $506$ is attainable by every sequence. WLOG there are at least $1011$ positive numbers in the sequence. Then we choose $+1$ whenever we can. Let the sequence be $c_1,b_1,\dots, c_n,b_n$ where $c_i$ are ...
1 comment
Read more

IMO Shortlist 2021 C1

 I am planning to do at least one ISL every day so that I do not lose my Olympiad touch (and also they are fun to think about!). Today, I tried the 2021 IMO shortlist C1.  (2021 ISL C1) Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$. Suppose not. Then any $3$ elements $x,y,z\in S$ will be $(x,y)=(y,z)=(x,z)$ or $(x,y)\ne (y,z)\ne (x,z)$. There exists an infinite set $T$ such that $\forall x,y\in T,(x,y)=d,$ where $d$ is constant. Fix a random element $a$. Note that $(x,a)|a$. So $(x,a)\le a$.Since there are infinite elements and finite many possibilities for the gcd (atmost $a$). So $\exists$ set $T$ which is infinite such that $\forall b_1,b_2\in T$ $$(a,b_1)=(a,b_2)=d.$$ Note that if $(b_1,b_2)\ne d$ then we get a contradiction as we get a set satisfying the proble...
1 comment
Read more

Geometry ( Finally!!!)

 This is just such an unfair blog.  Like if one goes through this blog, one can notice how dominated  Algebra is!! Like 6 out of 9 blog post is Algebra dominated -_- Where as I am not a fan of Algebra, compared to other genres of Olympiad Math(as of now). And this was just injustice for Synthetic Geo. So this time , go geo!!!!!!!!!!!  These problems are randomly from A Beautiful Journey through Olympiad Geometry.  Also perhaps I will post geo after March, because I am studying combi.  Problem:  Let $ABC$ be an acute triangle where $\angle BAC = 60^{\circ}$. Prove that if the Euler’s line of $\triangle ABC$ intersects $AB$ and $AC$ at $D$ and $E$, respectively, then $\triangle ADE$ is equilateral. Solution:  Since $\angle A=60^{\circ}$ , we get $AH=2R\cos A=R=AO$. So $\angle EHA=\angle DOA.$ Also it's well known that $H$ and $O $ isogonal conjugates.$\angle OAD =\angle EAH.$ By $ASA$ congruence, we get $AE=AD.$ Hence $\triangle ADE$ is equilateral....
3 comments
Read more

Symmetric Polynomials #week 6

Well... I haven't seen much symmetric polynomials in Olympiads, but still I am learning, because I found them cute. And I am basically using this blog as my notes :P What are symmetric polynomials?  One can understand this with  examples. If we are considering over 3 variables, $x_1,x_2,x_3$ then  $$\sum_{sym}x_1^2\cdot x_2^3\cdot x_3=x_1^2\cdot x_2^3\cdot x_3+x_1^2\cdot x_3^3\cdot x_2+x_2^2\cdot x_1^3\cdot x_3+x_2^2\cdot x_3^3\cdot x_1+x_3^2\cdot x_1^3\cdot x_2.$$ See? $3!$ terms! Let's take one more example with again over 3 variables, $x_1,x_2,x_3$ then $$\sum_{sym}x_1^2\cdot x_2^2= x_1^2\cdot x_2^2+x_1^2\cdot x_3^2+x_2^2\cdot x_1^2+x_2^2\cdot x_3^2+x_3^2\cdot x_1^2+x_3^2\cdot x_2^2$$ Wait.. why 2 times ? So basically what happens in symmetrictric sums, is we go through all $n!$ possible permutations. So, here we have $a^2\cdot b^2\cdot c^0$ as like the "general" form type, right? Now, list down all the $3!=6$ permutations of $x_1,x_2,x_3$, and put them in the gene...
3 comments
Read more

Number Theory Revise part 1

I thought to revise David Burton and try out some problems which I didn't do. It's been almost 2 years since I touched that book so let's see! Also, this set of problems/notes is quite weird since it's actually a memory lane. You will get to know on your own! I started with proving a problem, remembered another problem and then another and so on! It was quite fun cause all these questions were the ones I really wanted to solve! And this is part1 or else the post would be too long. Problem1: Prove that for $n\ge 1$  $$\binom{n}{r}<\binom{n}{r+1}$$ iff $0\le r\le \frac{n-1}{2}$ Proof: We show that $\binom{n}{r}<\binom{n}{r+1}$ for $0\le r\le \frac{n-1}{2}$ and use the fact that $$\binom{n}{n-r}=\binom{n}{r}$$ Note that $\binom{n}{r}= \frac{n!}{r!(n-r)!}, \binom{n}{r+1}=\frac{n!}{(r+1)!(n-r-1)!}$  Comparing, it's enough to show that $$\frac{1}{n-r}<\frac{1}{r+1}\text{ or show } n-r>r+1$$ which is true as $0\le r\le \frac{n-1}{2}$ Problem2: Show that the exp...
8 comments
Read more

IMO 2023 P2

IMO 2023 P2 Well, IMO 2023 Day 1 problems are out and I thought of trying the geometry problem which was P2.  Problem: Let $ABC$ be an acute-angled triangle with $AB < AC$. Let $\Omega$ be the circumcircle of $ABC$. Let $S$ be the midpoint of the arc $CB$ of $\Omega$ containing $A$. The perpendicular from $A$ to $BC$ meets $BS$ at $D$ and meets $\Omega$ again at $E \neq A$. The line through $D$ parallel to $BC$ meets line $BE$ at $L$. Denote the circumcircle of triangle $BDL$ by $\omega$. Let $\omega$ meet $\Omega$ again at $P \neq B$. Prove that the line tangent to $\omega$ at $P$ meets line $BS$ on the internal angle bisector of $\angle BAC$. Well, here's my proof, but I would rather call this my rough work tbh. There are comments in the end! Proof Define $A'$ as the antipode of $A$. And redefine $P=A'D\cap (ABC)$. Define $L=SP\cap (PDB)$.  Claim1: $L-B-E$ collinear Proof: Note that $$\angle SCA=\angle SCB-\angle ACB=90-A/2-C.$$ So $$\angle SPA=90-A/2-C\implies \ang...
2 comments
Read more

Reflecting on past

INMO Scores are out!! I am now a two times INMO awardee :) I got 16|0|1, so 17 in total! Yes, 16 in P1 T_T. I was thinking I would lose marks because of the way I wrote.  Lemme tell ya'll what happened that day but first I should share a few thoughts I had before the exam. My thoughts Honestly, my preparation for INMO was bad. In fact, I should say I didn't work hard at all. As I have said earlier, I had lost all my hopes for INMO and Olympiads as a whole after EGMO TSTs happened.  Art by Jelena Janic EGMO TSTs i.e European Girl's Mathematical Olympiad Team selection Tests 2022.  Literally my thoughts after EGMO TSTs I feel very ashamed to share but I got 1 mark in my EGMO TSTs. Tests in which I literally gave my whole life. I did so many ISLs ( like SO MANY), I mocked EGMO 2021 TST where my score was 28/42 and I perfected Day 2. 1 mark in the TST just showed my true potential. There are way better people than me in olys. A friend even said to me, "If I wouldn't...
7 comments
Read more

INMO Scores and Results

Heya! INMO Results are out! Well, I am now a 3 times IMOTCer :D. Very excited to meet every one of you! My INMO score was exactly 26 with a distribution of 17|0|0|0|0|9, which was a fair grading cause after problem 1, I tried problem 6 next. I was hoping for some partials in problem 4 but didn't get any.  I am so so so excited to meet everyone! Can't believe my olympiad journey is going to end soon..  I thought to continue the improvement table I made last year! ( I would still have to add my EGMO performance and also IMO TST performance too) 2018-2019[ grade 8]:  Cleared PRMO, Cleared RMO[ State rank 4], Wrote INMO 2019-2020[ grade 9]:  Cleared PRMO, Cleared RMO[ State topper], Wrote INMO ( but flopped it) 2020-2021[grade 10]:  Cleared IOQM, Cleared INMO [ Through Girl's Quota] 2021-2022[grade 11]:  Wrote EGMO 2022 TST[ Rank 8], Qualified for IOQM part B directly, Cleared IOQM-B ( i.e INMO) [Through general quota],  2022-2023 [grade 12]:  Wrote E...
Post a Comment
Read more