10-20 Two Coloring

A graph can be “colored” with N colors if you can paint every vertex with one of the N colors and have no edge between vertices of the same color. We will use integers to represent colors, like 0=red, 1=green, etc. (The actual colors do not matter.)

    from typing import Dict, Optional
    from graph import Vertex, Graph

  1. Produce an example to show you understand this

  2. Write a function

     def two_color(g: Graph) -> Optional[Dict[Vertex, int]]
     return None

    that produces a two coloring for a graph, or None if the graph cannot be two-colored.

Examples

The graph below can be colored with two colors.

The dictionary produced by two_color from that coloring, using 0 for blue and 1 for orange, would be {0:1, 1:1, 2:1, 3:0, 4:0, 5:0, 6:0, 7:1}.

An example of a graph that cannot be colored with two colors is the five vertex graph below.

The result of running two_color on that graph would be None.