Graph Coloring Basics

The four-color theorem's proof was significant because _________________________.

• it showed that the world is round

• it cost a lot of money

• it was the first proof that was computer aided

• it took so long to write

Any planar map can be colored with _____ or fewer colors.

• 5

• 4

• 3

• 2

Vertex coloring may require ______________ 4 colors.

• more than

• less than

A _______________ of a graph colors vertices k colors so that adjacent vertices are different color.

• chromatic number

• graph coloring

• k-coloring

• vertex coloring

The smallest number of colors needed to color a graph is called the ______________________.

• chromatic number

• graph coloring

• k-coloring

• vertex coloring

A graph in which each vertex is connected to every other vertex a _______________________.

• chromatic number

• circuit

• complete graph

• vertex-edge graph

In a complete graph, the chromatic number is ____________.

• 2

• 3

• the number of edges

• the number of vertices

In a circuit, the chromatic number is __________.

• always 2

• always 4

• 2 for even vertices and 3 for odd vertices

• the highest degree of any one vertex

What is the chromatic number of this graph?

• 2

• 3

• 4

• 5

What is the chromatic number of this graph?

• 2

• 3

• 4

• 5