Graph Coloring Basics

Front

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

Back

it was the first proof that was computer aided

Front

Any planar map can be colored with $4$ or fewer colors.

Back

4

Front

Vertex coloring may require ______________ 4 colors.

Back

more than

Front

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

Back

k-coloring

Front

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

Back

chromatic number

Front

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

Back

complete graph

Front

In a complete graph, the chromatic number is ____________.

Back

the number of vertices

Front

In a circuit, the chromatic number is __________.

Back

2 for even vertices and 3 for odd vertices

Front

What is the chromatic number of this graph?

Back

4

Front

What is the chromatic number of this graph?

Back

3