- Answers to Exercises 277
12 Euler’s Formula
12.1 A Planet Under Attack
12.1.1. There arennodes of degreen−1 and
(n
4)
nodes of degree 4
(see Section 11.1). So the number of edges is^12
(
n·(n−1) +(n
4)
· 4
)
. From
Euler’s Formula, the number of countries is
(
2(
n
4)
+
(
n
2))
−
(
n+(
n
4))
+2=
(
n
4)
+
(
n
2)
−n+2;you have to subtract 1 for the country outside.
12.1.2. Letfbe the number of regions of the island. Consider the graph
formed by the dams and also the boundary of the island. There are 2nnodes
of degree 3 (along the shore), and
(n
2)
nodes of degree 4 (the intersection
points of straight dams). So the number of edges is
1
2(
(2n)·3+(
n
2)
· 4
)
=2
(
n
2)
+3n.The number of countries isf+1 (we have to count the ocean too), so Euler’s
formula givesf+1+2n+
(n
2)
=2
(n
2)
+3n+ 2, whencef=(n
2)
+n+1.12.2 Planar Graphs
12.2.1. Yes, see Figure 16.2.
FIGURE 16.2.12.2.2. No; the argument is similar to the one showing thatK 5 is not
planar. The houses, wells, and paths form a bipartite graph with 6 nodes
and 9 edges. Suppose that this can be drawn in the plane without inter-
sections. Then we have 9 + 2−6 = 5 regions. Each region has at least 4
edges (since there are no triangles), and hence the number of edges is at
least^12 · 5 ·4 = 10, which is a contradiction.