Question about circuits in a planar graph (length)

567 Views Asked by At

I need to show that a circuit in a planar graph that encloses two regions, and each region has an even number edges, has an even length.

Could someone point me in the right direction as to how to start this problem, please?

1

There are 1 best solutions below

0
On BEST ANSWER

I'm assuming the two regions are enclosed by two cycles $C_1, C_2$ that have common edges that lie on a path $P$ that separates the two regions. You'll want to show that removing the common edges leaves a cycle of even length, in other words if $|E(C_1)|$ and $|E(C_2)|$ are even then it follows that $|E(C_1)|$ + $|E(C_2)| - 2|E(P)|$ is even.