Chapter Summary

Which of the graphs in the previous question contain Euler paths or circuits? Which of the graphs are planar?

Draw a graph which has an Euler circuit but is not planar.

Draw a graph which does not have an Euler path and is also not planar.

If a graph has 10 vertices and 10 edges and contains an Euler circuit, must it be planar? How many faces would it have?

Suppose $G$ is a graph with $n$ vertices, each having degree 5.

1. For which values of $n$ does this make sense?

2. For which values of $n$ does the graph have an Euler path?

3. What is the smallest value of $n$ for which the graph might be planar? (tricky)

At a school dance, 6 girls and 4 boys take turns dancing (as couples) with each other.

1. How many couples danced if every girl dances with every boy?

2. How many couples danced if everyone danced with everyone else (regardless of gender)?

3. Explain what graphs can be used to represent these situations.

Among a group of $n$ people, is it possible for everyone to be friends with an odd number of people in the group? If so, what can you say about $n$?

Your friend has challenged you to create a convex polyhedron containing 9 triangles and 6 pentagons.

1. Is it possible to build such a polyhedron using only these shapes? Explain.

2. You decide to also include one heptagon (seven-sided polygon). How many vertices does your new convex polyhedron contain?

3. Assuming you are successful in building your new 16-faced polyhedron, could every vertex be the joining…

Is there a convex polyhedron which requires 5 colors to properly color the vertices of the polyhedron? Explain.

How many edges does the graph $K_{n,n}$ have? For which values of $n$ does the graph contain an Euler circuit? For which values of $n$ is the graph planar?

The graph $G$ has 6 vertices with degrees $1, 2, 2, 3, 3, 5$. How many edges does $G$ have? If $G$ was planar how many faces would it have? Does $G$ have an Euler path?

What is the smallest number of colors you need to properly color the vertices of $K_{7}$. Can you say whether $K_7$ is planar based on your answer?

What is the smallest number of colors you need to properly color the vertices of $K_{3,4}$? Can you say whether $K_{3,4}$ is planar based on your answer?

Prove that $K_{3,4}$ is not planar. Do this using Euler's formula, not just by appealing to the fact that $K_{3,3}$ is not planar.

A dodecahedron is a regular convex polyhedron made up of 12 regular pentagons.

1. Suppose you color each pentagon with one of three colors. Prove that there must be two adjacent pentagons colored identically.

2. What if you use four colors?

3. What if instead of a dodecahedron you colored the faces of a cube?

Decide whether the following statements are true or false. Prove your answers.

1. If two graph $G_1$ and $G_2$ have the same chromatic number, then they are isomorphic.

2. If two graphs $G_1$ and $G_2$ have the same number of vertices and edges and have the same chromatic number, then they are isomorphic.

3. If two graphs are isomorphic, then they have the same chromatic number.

If a planar graph $G$ with $7$ vertices divides the plane into 8 regions, how many edges must $G$ have?

For each part below, say whether the statement is true or false. Explain why the true statements are true, and give counterexamples for the false statements.

1. Every bipartite graph is planar.

2. Every bipartite graph has chromatic number 2.

3. Every bipartite graph has an Euler path.

4. Every vertex of a bipartite graph has even degree.

5. A graph is bipartite if and only if the sum of the degrees of all the vertic…

Consider the statement “If a graph is planar, then it has an Euler path.”

1. Write the converse of the statement.

2. Write the contrapositive of the statement.

3. Write the negation of the statement.

4. Is it possible for the contrapositive to be false? If it was, what would that tell you?

5. Is the original statement true or false? Prove your answer.

6. Is the converse of the statement true or false? Prove your answer.