Print preview
Worksheet 5.4 Planar or Not?
A graph with \(6\) vertices. The adjacencies are given below.
| Vertex | Neighbors |
| \(1\) | \(3\text{,}\) \(4\text{,}\) \(5\) |
| \(2\) | \(3\text{,}\) \(4\text{,}\) \(5\) |
| \(3\) | \(1\text{,}\) \(2\text{,}\) \(4\text{,}\) \(6\) |
| \(4\) | \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(6\) |
| \(5\) | \(1\text{,}\) \(2\text{,}\) \(4\text{,}\) \(6\) |
| \(6\) | \(3\text{,}\) \(4\text{,}\) \(5\) |
A graph with 10 vertices labeled 0 to 9. For the vertices with labels 0 through 4, the vertex with label \(i\) has neighbors \(i-1\text{,}\) \(i+1\text{,}\) and \(i+5\text{.}\) The first two adjacencies are interpreted cyclically so that, for instance, \(4\) has neighbors \(3\) and \(0\text{.}\) For the vertices with labels 5 through 9, the vertex with label \(i\) has neighbors \(i-5\text{,}\) \(i+2\text{,}\) and \(i+3\text{.}\) The second and third adjacencies are interpreted cyclically so that, for instance, \(9\) has neighbors \(6\) and \(7\text{.}\)
A graph with \(8\) vertices. The adjacencies are given below.
| Vertex | Neighbors |
| \(1\) | \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(6\) |
| \(2\) | \(1\text{,}\) \(4\text{,}\) \(6\) |
| \(3\) | \(1\text{,}\) \(4\text{,}\) \(7\) |
| \(4\) | \(2\text{,}\) \(3\text{,}\) \(7\text{,}\) \(8\) |
| \(5\) | \(1\text{,}\) \(6\text{,}\) \(7\) |
| \(6\) | \(1\text{,}\) \(2\text{,}\) \(5\text{,}\) \(8\) |
| \(7\) | \(3\text{,}\) \(4\text{,}\) \(5\text{,}\) \(8\) |
| \(8\) | \(4\text{,}\) \(6\text{,}\) \(7\) |
A graph with \(8\) vertices. The vertices are arranged at the vertices of a regular octagon. Each vertex has degree \(5\text{.}\) The five neighbors are the two immediately adjacent (on on either side) around the octagon as well as the three opposite. For example, vertex \(1\) has neighbors \(2\) and \(8\) (adjacent on the octagon) and \(4, 5, 6\) (opposite on the octagon).
A graph with \(8\) vertices. The adjacencies are given below.
| Vertex | Neighbors |
| \(1\) | \(2\text{,}\) \(3\text{,}\) \(4\text{,}\) \(5\text{,}\) \(6\text{,}\) \(7\) |
| \(2\) | \(1\text{,}\) \(3\text{,}\) \(4\text{,}\) \(5\text{,}\) \(6\text{,}\) \(8\) |
| \(3\) | \(1\text{,}\) \(2\text{,}\) \(4\text{,}\) \(5\text{,}\) \(7\text{,}\) \(8\) |
| \(4\) | \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(6\text{,}\) \(7\text{,}\) \(8\) |
| \(5\) | \(1\text{,}\) \(2\text{,}\) \(3\text{,}\) \(6\text{,}\) \(7\text{,}\) \(8\) |
| \(6\) | \(1\text{,}\) \(2\text{,}\) \(4\text{,}\) \(5\text{,}\) \(7\text{,}\) \(8\) |
| \(7\) | \(1\text{,}\) \(3\text{,}\) \(4\text{,}\) \(5\text{,}\) \(6\text{,}\) \(8\) |
| \(8\) | \(2\text{,}\) \(3\text{,}\) \(4\text{,}\) \(5\text{,}\) \(6\text{,}\) \(7\) |
A graph with 8 vertices. The adjacencies are given below.
| Vertex | Neighbors |
| \(1\) | \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(8\) |
| \(2\) | \(1\text{,}\) \(4\text{,}\) \(6\text{,}\) \(7\) |
| \(3\) | \(1\text{,}\) \(4\text{,}\) \(6\text{,}\) \(7\) |
| \(4\) | \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(8\) |
| \(5\) | \(1\text{,}\) \(4\text{,}\) \(6\text{,}\) \(7\) |
| \(6\) | \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(8\) |
| \(7\) | \(2\text{,}\) \(3\text{,}\) \(5\text{,}\) \(8\) |
| \(8\) | \(1\text{,}\) \(4\text{,}\) \(6\text{,}\) \(7\) |
-
The graph \(\bfG_1\) is not planar, as it contains a \(\bfK_{3,3}\text{.}\) In fact, this graph is \(\bfK_{3,3}\) plus two additional edges (\(45\) and \(34\text{.}\))
-
\(\bfG_2\) is not planar, but this is tougher to see. Refer to Figure 5.10, where we illustrate a \(\bfK_{3,3}\) subdivision. The vertex \(8\text{,}\) which is shown in magenta, is not required for the \(\bfK_{3,3}\) subdivision. The yellow vertices \(\set{0,2,9}\) form one side of the \(\bfK_{3,3}\) while \(\set{1,4,7}\) form the other. The dashed edges through the gray vertices (\(05,57, 16,69, 23,34\)) are the disjoint paths that, when combined with the edges around the outside of the hexagon (\(04,49,97,72,21,10\)) complete the \(\bfK_{3,3}\) subdivision.
-
The graph \(\bfG_4\) is not planar, as it has \(5\cdot 8/2 = 20\) edges and \(8\) vertices, but \(3\cdot 8-6 = 18\text{.}\) Thus, it has too many edges to be planar.
-
The graph \(\bfG_5\) is not planar because it has \(6\cdot 8 /2 = 24\) edges and \(8\) vertices, but \(3\cdot 8-6 = 18\text{.}\) Thus, it has too many edges to be planar.
-
The graph \(\bfG_6\) is not planar because it contains \(\bfK_{3,3}\text{.}\) As one example of a \(\bfK_{3,3}\text{,}\) put \(\set{2,5,8}\) in one set and \(\set{4,6,7}\) in the other. We then have an edge from each vertex of the first set to each vertex of the second set.
A planar drawing of the graph \(\bfG_2\) formed by adding the diagonals to two opposite faces of a cube.
A drawing of the Petersen graph that emphasizes the \(\bfK_{3,3}\) subdivision it contains. The text contains more details about this image.
