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💜