11 a Show that if a circuit in a planar graph encloses exact

11. (a) Show that if a circuit in a planar graph encloses exactly two regions each of which has an even number of boundary edges, then the circuit has even length.

Solution

Solution :- (b) The circuit has even length that is same as bipartite.

a graph is bipartite if and only if all circuits have even length.

So if we can show that all circuits in our graph G have even length, we will be done.

Assume every region in a planar graph G has an even number of bounding edges.

Let H be a circuit in G, of length |H|.

Case 1 ) Consider the regions inside H, of degrees r₁, r₂,..., r_k. Each of the r_i is even by hypothesis.

Let us count the sum r₁ + r₂ + ... + r_k in a different way. First, count the edges of H ; there are |H| of them.

Now each edge that is completely inside H bounds two of the regions inside H ,

and so must be counted twice in r₁ + r₂ + ... + r_k.

If there are m edges completely inside H , this yields

r₁ + r₂ + ... + r_k = |H| + 2m |H|   = r₁ + r₂ + ... + r_k - 2m.

Since each summand on the right-hand side of the last equation is even, |H| must be even.

Case 2 ) Use induction on the number of regions enclosed by H .

If H only encloses one region, then |H| is even by hypothesis.

So assume any circuit bounding k - 1 1 regions has even length.

Assume there are k regions inside H. Consider a region R which shares at least one edge with H.

Create a new circuit H\' which shares all edges with H except that it uses all edges of R that H doesn\'t use,

and doesn\'t use the edges of R that H uses. Then R is on the outside of H\', and H\' has k - 1 regions inside it.

By the inductive hypothesis, H\' has even length. Finally, let r be the number of edges of R used by H,

and let r\' be the number of edges of R used by H\'. Then r + r\' is the number of bounding edges of R,

which is even by assumption; therefore r - r\' is even also; and so |H| = |H\'| + r - r\' is even.