Prove that every planar graph G decomposes into two bipartit

Prove that every planar graph G decomposes into two bipartite graphs. As in edge decomposition.

Solution

This example is equivalent to Four Color Theorem.

Proof. Assuming the 4 color theorem, let a planar graph G = (V; E) with vertex

Set V and edge set E be four-colored using for colors the ordered pairs

aa; ab; ba; bb

Let G1 = (V; E1) and G2 = (V; E2), where the edges in E1 are chosen to be those edges in E of the form faa; bag, fab; bbg and fab; bag, and the edges in E2 are the remaining

edges, namely those colored faa; abg, fba; bbg and faa; bbg. Observing that

the vertices of the edges in E1 have colors differing in the