Graph Theory Review Sheet Template (Page 3 of 4) in pdf

Graph Theory Review Sheet Template Page 3

3. Which of the following lists of numbers could be degrees of vertices in a graph?

a. 2, 3, 4, 3, 5, 6, 7

b. 2, 2, 4, 4, 6, 6, 5, 2, 3

c. 0, 0, 0, 0, 0, 1, 1

d. 3, 5, 7, 3, 9, 3, 2, 5

4. Draw an example of a planar graph that is 4-colorable but not 3-colorable. Can you draw an example

of a planar graph that is 5-colorable but not 4-colorable?

5. A connected planar graph has 11 vertices and 18 edges. How many faces must it have?

6. A connected planar graph has 14 edges and 8 faces. How many vertices must it have?

7. A planar graph has 12 vertices, 7 faces, and 2 components. How many edges must this graph have?

8. A connected planar graph has vertices of degrees 2, 3, 3, 4, 5, 6, and 7. Find the number of edges and

the number of faces for the graph.

9. A connected planar graph has 7 faces; 3 of the faces have degree 4, 2 of the faces have degree 3 and 2

of the faces have degree 2. How many edges does the graph have?

10. The Paper Street Soap Co. has 6 employees; Bob, Cornelius, Jack, Marla, Rupert, and Tyler. The

boss needs to meet with groups of employees to discuss a new overtime policy, but unfortunately some

employees can’t stand to be in the same room with others. In the table below, an X means that those

two people can’t stand each other, and can’t be in the same room together.

–

Make a graph with vertices the employees and an edge between vertices if those employees hate each

other. Determine the chromatic number of the graph. What does this say about the number of diﬀerent

separate meetings the boss must make with the employees.

Graph Theory Review Sheet Template Page 3