# Challenge: Color the Graph

Use the fewest possible colors, to color the vertices of a graph such that no two adjacent vertices are the same color.

## We'll cover the following

## Problem statement

Graph coloring involves finding a way of coloring the vertices of a graph.

Implement a function that finds a way of coloring a graph so that no two adjacent vertices are colored using the same color. Try using the **minimum** number of colors possible.

### Input

The input is an **undirected** graph with no colors assigned.

### Output

The output is a graph with all of its vertices colored in the correct way, using the **minimum** number of colors possible.

### Sample input

**Graph:**

```
graph {0 -- 1
0 -- 2
1 -- 2
1 -- 3
2 -- 3
3 -- 4}
```

### Sample output

```
Vertex 0 , Color 0
Vertex 1 , Color 1
Vertex 2 , Color 2
Vertex 3 , Color 0
Vertex 4 , Color 1
```

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.