Section 6.1 Graphs and Their Representations
503
30. If all the nodes of a simple, connected, planar graph have degree 4 and the number of arcs is 12, into how
many regions does it divide the plane?
31. Does Euler’s formula (Equation (1) of the theorem on the number of nodes and arcs) hold for nonsimple
graphs? What about inequalities (2) and (3) of the theorem?
32. What is wrong with the following argument that claims to use elementary subdivisions to turn a nonplanar
graph into a planar graph?
In a nonplanar graph there must be two arcs a i and a j that intersect at a point v that is not a node. Do
an elementary subdivision on a i with an inserted node at v and an elementary subdivision on a j with an
inserted node at v. In the resulting graph, the point of intersection is a node. Repeat this process with any
non-node intersections; the result is a planar graph.
For Exercises 33–36, determine whether the graph is planar (by finding a representation where arcs intersect
only at nodes) or nonplanar (by finding a subgraph homeomorphic to K 5 or K 3,3 .
33.
35.
34.
36.
2
1
5
3
7
4
6
For Exercises 37–42, write the adjacency matrix for the given graph.
37.
5
2
3
4
1
39.
2
4
5
1
3
6
7
38.
1
2
4
5
3
40.
1
4
5
2
3
6