Explore BrainMass

Explore BrainMass

    Graphs : Coloring Maps

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Show that a planar map M = M(G) can be 2 colored iff every vertex of G has even degree.

    [The map M(G) of a graph G is the collection of its faces, which are to be colored so that no adjacent faces have the same color.]

    [hint: if every vertex of G has even degree then G is a union of edge-disjoint cycles. for another solution, apply induction on the number of edges, and delete the edges of a cycle forming the boundry of a face of M(G).]

    © BrainMass Inc. brainmass.com December 24, 2021, 7:01 pm ad1c9bdddf
    https://brainmass.com/math/graphs-and-functions/graphs-coloring-maps-157578

    SOLUTION This solution is FREE courtesy of BrainMass!

    Please see the attached file for the complete solution.
    Thanks for using BrainMass.

    Proof : Let G we any graph of 2 face colourable. Then dual graph of G., i.e. G* having chromatic number (G)= 2. Therefore G* is a bipartite graph. Note that every graph is bipartite if and only if it has chromatic number 2. And every dual of bipartite graph is Euler graph and every Euler graph having vertex of even degree. And we also know that G is isomorphic to G**

    Where G** is dual of G*
    .
    Thus every vertex of G has even degree.

    Conversely, let G be a graph having even degree vertex. Then G** (double dual of G) is Euler graph. Therefore G* is bipartite. And since G* is bipartite therefore chromatic number of G is 2 i.e, (G*) =2 and therefore G is two face colourable.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    © BrainMass Inc. brainmass.com December 24, 2021, 7:01 pm ad1c9bdddf>
    https://brainmass.com/math/graphs-and-functions/graphs-coloring-maps-157578

    Attachments

    ADVERTISEMENT