Graph Theory - chromatic number

675 Views Asked by At

Draw a planar graph that is 4-chromatic that has both a Hamilton circuit and a Euler cycle. Assign appropriate colors to each vertex and denote a Hamilton circuit and Euler cycle that are present.

I currently have a graph that is a square with 4 edges. Would this work?

1

There are 1 best solutions below

2
On BEST ANSWER

A complete graph on $4$ vertices is $4$-chromatic and has a Hamiltonian cycle.

To complete the example, ensure it has an Eulerian cycle by simply drawing an extra edge between each of two pairs of vertices.