Proving Graph Theory Question

Mathematics Asked by Maddy on September 15, 2020

I am not able to come up with a proof regarding this statement –

Consider G be a connected planar graph. If G is not bipartite, then any planar embedding of G has at least 2 faces with odd degree.

Can someone help me with the proof?

One Answer

Since G is not bipartite, G contains an odd cycle C. Let $F_{1},F_{2},......,F_{k}$ be the faces inside C in the planar embedding. Consider the sum of the degrees of these face.

  • Each edge in C is being counted once.
  • Let D be the set of edges on any boundary of any $F_{i}$, but not on C.

Each edge in D is counted twice.

So $sum_{i}$ $deg(F_{i})$ = $|E(C)| + 2|D|$

Since $|E(C)|$ is odd and $2|D|$ is even,

$sum_{i}$ $deg(F_{i})$ is odd, so $deg(F_{i})$ must be odd for some $i$

So at least one face inside C has odd degree.

The same argument can be used to show that at least once face outside C has odd degree.

Correct answer by Prabh Simran Singh Badwal on September 15, 2020

Add your own answers!

Related Questions

How to calculate autocorrelation at certain lag?

0  Asked on December 6, 2021 by hillbilly-joe


Combining team probabilities

0  Asked on December 6, 2021 by gav


Question on the proof of Theorem 7-1 in Spivak’s Calculus

1  Asked on December 5, 2021 by toronto-hrb


Guided Integration Question

2  Asked on December 5, 2021 by punkindrublic


Residue Theorem Integral

1  Asked on December 5, 2021 by anubhav-nanavaty


What does “Parameterizations are not unique” mean here?

1  Asked on December 5, 2021 by slangevar


Rank of non-negative matrices

0  Asked on December 5, 2021 by hrushikesh-mhaskar


Ask a Question

Get help from others!

© 2023 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP