Exercise 20.

Consider the graph below:

A graph with six vertices. Two vertices are aligned in a center column, and are adjacent to each other. Each is also adjacent to each of the other four vertices.

  1. Does the graph have an Euler path or circuit? Explain.

  2. Is the graph planar? Explain.

  3. Is the graph bipartite? Complete? Complete bipartite?

  4. What is the chromatic number of the graph.

Solution.
in-context