Graph Theory: Planar Graphs

Continuing from the previous post ( which is here ). This is a bit short post. I think this post is not at all helpful in olys but then let's do it cause I find them interesting :P. Here are my notes..

Book referred: Daniel A Marcus Graph theory

Chapter H:

Planar Graphs: A planar graph is a graph that can be represented by a diagram with no edge cross. Such a diagram is called a plane diagram. For $K_4$ is a planar graph.
Regions formed by a graph: The planar graph divides the plan into regions
Non- planar graph: A non-planar graph is a graph that always has a edge cross.
Regional Degrees: The regions are boundaries by edges. The number od edges each region is boundaries with is called regional degrees.
Subdivision: A graph that is obtained by inserting vertices of degree $2$ is an already existing edge.

Regional Degree theorem: Let $G$ be a connected graph and let $r_1,r_2,\dots $ be the degrees of the regions in any plane diagram of $G.$ Then the sum of $$r_1+r_2+r_3+\dots =2e$$

Proof: Note that each edges contributes two times in the region sum, since it's part of two regions. ( True for multi graph too)

Funfact: Let $G$ be a connected graph with three or more vertices. Then in any plane of diagrams of $G,$ every region has degree greater than or equal to $3.$

Regions and each edge contribute to two

Euler's Formula: Let $G$ be a connected planar graph with $v$ vertices and $e$ edges and $r$ be the number of regions in any plane diagram $G.$ Then $$v-e+r=2.$$

More on Euler's formula: We can extend it to solid to reknown formula $$v-e+f=2.$$

Proof: We consider a spanning tree of the connected graph. It exist as the graph is connected. Note that now we have $$v-e+r= v-(v-1)+1=2.$$

Now, whenever we add an edge, we get a new cycle and hence a new region. So the $-e+r$ is constant.

Another proof: Reduce the graph into spanning tree by removing one edge from a cycle and same reasoning.

Problem 1: Prove that $K_5$ is non planar.

Proof: Suppose it is planar, then since $K_5$ is connected, it must satisfy the Euler's formula. So $$v-e+r=2\implies r= 7$$

But by the funfact, the regional degree sums must be $\ge 7\cdot 3=21$ but regional degree sum is $2e=20.$ Contradiction.

Problem 2: Let $G$ be a connected graph with three or more vertices. Show that $r\le 2e/3$ and prove that $e\le 3v-6.$

Proof: For the first inequality we use the fact that each region is bondried by atleats $3$ edges. And $$2e=\sum r_i, r_i\ge 3 \implies r\le 2e/3.$$ Using euler's formula, we get $$ v-e+r=2\implies v-e+2e/3\ge 2\implies 3v-6 \ge e$$

Problem 3: In any plane diagram of a bipartite graph, all of the regional degrees must be even.

Proof: Consider the boundaries of any region. Since it is a bipartite graph, colour the vertices with two colour such that no two adjacent vertices are of the same colour. So the boundaries must have even length i.e even degree.

Problem 4: Suppose $G$ is bipartite Show that $r\le e/2$ and $e\le 2v-4.$

Prooof: Since $G$ is bipartite, the regional degree must be at least $4$ so $$r\le \frac{2e}{4}=\frac{e}{2}.$$

Using Euler's Formula, we get $$ v-e+r=2\implies v-e +\frac{e}{2}\ge 2\implies 2v-e\ge 4$$

So $$e\le 2v-4.$$

Problem 5: Prove that $K_{3,3}$ is non planar.

Proof: Suppose it is planar, then since $K_{3,3}$ is connected, it must satisfy the Euler's formula.

By euler's formula, we get $$v-e+r=2\implies r= 5.$$ Since, we have bipartite graph, we get $r\le e/2 $ but $5\ge 9/2.$

Non planar graphs [intuitive idea]:

When we add a degree two vertex to a non plannar graph $G$, the new subdivision graph $G'$ would be non plannar. In order to make $G$ a planar graph, we would have to add vertex in the "intersection" of the edges, which have degree $4.$

Moreover, if the subdivision $G'$ of the graph $G$ is planar then $G$ is planar too. The only case it wont be planar is when we remove the vertex from $G'$ which forms the intersection point. But then this vertex would have degree $4$ at least. Hence it is not the point we added so form the subdivision.

Hence, if one graph is a subdivision of another, then either both graphs are planar or else both are non planar.

Subdivision of $K_5$

Problem: If a graph $G$ contains a subgraph with is either $K_{3,3}$ or $K_5$ or a subdivision of one of these, then $G$ must be non -planar.

This just works, because we know the subdivision would be non planar.

Now, here's the black magic! I don't know the proof of this theorem though..

Kuratowski's Theorem: Every non planar contains a subgraph which is either $K_5$ or $K_{3,3}.$

Using this theorem, we can show that a Petersen graph non planar too.

The Petersen graph is non planar

Problem: Show that the Petersen graph is non-planar

Proof: Refer to the below image

We use the subdivision fact and the fact that $K_{3,3}$ is non-planar. By Kuratowski's Theorem we are done.

Yayy!! That's it for this blog post, I think there will be a sequel talking about vertex colouring which I am so excited to learn!

Sunaina💜

Comments

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...

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...

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 ...

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...

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....

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...

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...

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...

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...

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...

Sunaina thinks absurd

Search This Blog