# Proving Graph Theory Question

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.

## Related Questions

### The zero(s) of a vector-valued multivariable function

1  Asked on December 6, 2021 by yyzheng

### Closed curve not passing origin and winding number (complex analysis)

1  Asked on December 6, 2021 by 10understanding

### How to calculate autocorrelation at certain lag?

0  Asked on December 6, 2021 by hillbilly-joe

### How do you solve $|x+1| < |3^x + 5|$?

3  Asked on December 6, 2021

### Combining team probabilities

0  Asked on December 6, 2021 by gav

### Is there a general way to determine whether the nth partial sum of a series has an explicit, closed-form representation?

1  Asked on December 5, 2021

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

1  Asked on December 5, 2021 by toronto-hrb

### Show that $limlimits_{Nrightarrowinfty}sumlimits_{n=1}^Nfrac{1}{N+n}=intlimits_1^2 frac{dx}{x}=ln(2)$

3  Asked on December 5, 2021 by coffeearabica

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

### stuck with how this ordinary differential equation changes in new coordinates?

1  Asked on December 5, 2021 by mathica

### Matrix exponential of a positive matrix

1  Asked on December 5, 2021

### Condition for the sum of two fractions to be irreducible

1  Asked on December 5, 2021 by nilotpal-sinha

### Will high school competition math materials help me prepare for the Putnam?

1  Asked on December 5, 2021 by whjjp

### $AD$ has exactly one negative eigenvalue if $v^T A v > 0$ and $D = mbox{diag}(-1,1,1)$

3  Asked on December 5, 2021

### Designing a Custom “Abbreviated Wheel” System for the Lottery

1  Asked on December 5, 2021

### What is the name for the distribution of values taken by a stochastic process?

0  Asked on December 5, 2021