Discrete MathematicsAn Open Introduction

The first and the third graphs are the same (try dragging vertices around to make the pictures match up), but the middle graph is different (which you can see, for example, by noting that the middle graph has only one vertex of degree 2, while the others have two such vertices).

The first (and third) graphs contain an Euler path. All the graphs are planar.

For example, \(K_5\text{.}\)

For example, \(K_{3,3}\text{.}\)

Yes. According to Euler's formula it would have 2 faces. It does. The only such graph is \(C_{10}\text{.}\)

1. Only if \(n \ge 6\) and is even.

2. None.

3. 12. Such a graph would have \(\frac{5n}{2}\) edges. If the graph is planar, then \(n - \frac{5n}{2} + f = 2\) so there would be \(\frac{4+3n}{2}\) faces. Also, we must have \(3f \le 2e\text{,}\) since the graph is simple. So we must have \(3\left(\frac{4 + 3n}{2}\right) \le 5n\text{.}\) Solving for \(n\) gives \(n \ge 12\text{.}\)

1. There were 24 couples: 6 choices for the girl and 4 choices for the boy.

2. There were 45 couples: \({10 \choose 2}\) since we must choose two of the 10 people to dance together.

3. For part (a), we are counting the number of edges in \(K_{4,6}\text{.}\) In part (b) we count the edges of \(K_{10}\text{.}\)

Yes, as long as \(n\) is even. If \(n\) were odd, then corresponding graph would have an odd number of odd degree vertices, which is impossible.

1. No. The 9 triangles each contribute 3 edges, and the 6 pentagons contribute 5 edges. This gives a total of 57, which is exactly twice the number of edges, since each edge borders exactly 2 faces. But 57 is odd, so this is impossible.

2. Now adding up all the edges of all the 16 polygons gives a total of 64, meaning there would be 32 edges in the polyhedron. We can then use Euler's formula \(v - e + f = 2\) to deduce that there must be 18 vertices.

3. If you add up all the vertices from each polygon separately, we get a total of 64. This is not divisible by 3, so it cannot be that each vertex belongs to exactly 3 faces. Could they all belong to 4 faces? That would mean there were \(64/4 = 16\) vertices, but we know from Euler's formula that there must be 18 vertices. We can write \(64 = 3x + 4y\) and solve for \(x\) and \(y\) (as integers). We get that there must be 10 vertices with degree 4 and 8 with degree 3. (Note the number of faces joined at a vertex is equal to its degree in graph theoretic terms.)

No. Every polyhedron can be represented as a planar graph, and the Four Color Theorem says that every planar graph has chromatic number at most 4.

\(K_{n,n}\) has \(n^2\) edges. The graph will have an Euler circuit when \(n\) is even. The graph will be planar only when \(n \lt 3\text{.}\)

\(G\) has 8 edges (since the sum of the degrees is 16). If \(G\) is planar, then it will have 4 faces (since \(6 - 8 + 4 = 2\)). \(G\) does not have an Euler path since there are more than 2 vertices of odd degree.

\(7\) colors. Thus \(K_7\) is not planar (by the contrapositive of the Four Color Theorem).

The chromatic number of \(K_{3,4}\) is 2, since the graph is bipartite. You cannot say whether the graph is planar based on this coloring (the converse of the Four Color Theorem is not true). In fact, the graph is not planar, since it contains \(K_{3,3}\) as a subgraph.

For all these questions, we are really coloring the vertices of a graph. You get the graph by first drawing a planar representation of the polyhedron and then taking its planar dual: put a vertex in the center of each face (including the outside) and connect two vertices if their faces share an edge.

1. Since the planar dual of a dodecahedron contains a 5-wheel, it's chromatic number is at least 4. Alternatively, suppose you could color the faces using 3 colors without any two adjacent faces colored the same. Take any face and color it blue. The 5 pentagons bordering this blue pentagon cannot be colored blue. Color the first one red. Its two neighbors (adjacent to the blue pentagon) get colored green. The remaining 2 cannot be blue or green, but also cannot both be red since they are adjacent to each other. Thus a 4th color is needed.

2. The planar dual of the dodecahedron is itself a planar graph. Thus by the 4-color theorem, it can be colored using only 4 colors without two adjacent vertices (corresponding to the faces of the polyhedron) being colored identically.

3. The cube can be properly 3-colored. Color the “top” and “bottom” red, the “front” and “back” blue, and the “left” and “right” green.

\(G\) has \(13\) edges, since we need \(7 - e + 8 = 2\text{.}\)

1. The graph does have an Euler path, but not an Euler circuit. There are exactly two vertices with odd degree. The path starts at one and ends at the other.

2. The graph is planar. Even though as it is drawn edges cross, it is easy to redraw it without edges crossing.

3. The graph is not bipartite (there is an odd cycle), nor complete.

4. The chromatic number of the graph is 3.

1. False. For example, \(K_{3,3}\) is not planar.

2. True. The graph is bipartite so it is possible to divide the vertices into two groups with no edges between vertices in the same group. Thus we can color all the vertices of one group red and the other group blue.

3. False. \(K_{3,3}\) has 6 vertices with degree 3, so contains no Euler path.

4. False. \(K_{3,3}\) again.

5. False. The sum of the degrees of all vertices is even for all graphs so this property does not imply that the graph is bipartite.

1. If a graph has an Euler path, then it is planar.

2. If a graph does not have an Euler path, then it is not planar.

3. There is a graph which is planar and does not have an Euler path.

4. Yes. In fact, in this case it is because the original statement is false.

5. False. \(K_4\) is planar but does not have an Euler path.

6. False. \(K_5\) has an Euler path but is not planar.