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?

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

1 Asked on December 6, 2021 by yyzheng

1 Asked on December 6, 2021 by 10understanding

0 Asked on December 6, 2021 by hillbilly-joe

1 Asked on December 5, 2021

1 Asked on December 5, 2021 by toronto-hrb

3 Asked on December 5, 2021 by coffeearabica

1 Asked on December 5, 2021 by anubhav-nanavaty

1 Asked on December 5, 2021 by slangevar

1 Asked on December 5, 2021 by mathica

chain rule coordinate systems derivatives ordinary differential equations

1 Asked on December 5, 2021

inequality linear algebra matrices matrix exponential positive matrices

0 Asked on December 5, 2021 by hrushikesh-mhaskar

1 Asked on December 5, 2021 by nilotpal-sinha

divisibility elementary number theory gcd and lcm number theory prime numbers

1 Asked on December 5, 2021 by saad-salman

computational mathematics gradient descent machine learning regression statistics

1 Asked on December 5, 2021 by whjjp

book recommendation contest math online resources reference request soft question

3 Asked on December 5, 2021

1 Asked on December 5, 2021

Get help from others!

Recent Answers

- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?

Recent Questions

- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?

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