Suppose there is a connected planar simple graph G with v vertices such that all its regions are triangles (a cycle consisting of three edges).

(a) Into how many regions does a representation of the planar graph G split the plane?

(b) Suppose the vertices of the planar graph G are colored in three colors. A region is called to be tricolored (or bicolored) if its vertices are colored in exactly three (or two) different colors. Similarly, a monocolored region is the one with all its vertices colored in exactly one color. Prove that the number of tricolored regions is always even no matter how the vertices are colored.

(Hint: If you place a new vertex inside a region (triangle) of G and connect it with all vertices of that region, then all regions are still triangles and the parity of the total number of regions stays the same.)

Answer rating: 100% (QA)

Solutions phen is il possi ble to goaph so that none of the edgg cross if this pl... View the full answer