276 16. Answers to Exercises
10.4 How to Find a Perfect Matching
10.4.1. On a path with 4 nodes, we may select the middle edge.
10.4.2. The edges in the greedy matchingMmust meet every edge in
G(otherwise, we could further extendM), in particular every edge in the
perfect matching matching. So every edge in the perfect matching has at
most one endpoint unmatched byM.
10.4.3. The largest matching has 5 edges.
10.4.4. If the algorithm terminates without a perfect matching, then the
setSshows that the graph is not “good.”
11 Combinatorics in Geometry
11.1 Intersections of Diagonals
11.1.1. n(n 2 −3).
11.2 Counting Regions
11.2.1. True forn= 1. Letn>1. Delete any line. The remaining lines
divide the plane into (n−1)n/2 + 1 regions by the induction hypothesis.
The last line cutsnof these into two. So we get
(n−1)n
2+1+n=
n(n+1)
2+1.
11.3 Convex Polygons
11.3.1. See Figure 16.1.
FIGURE 16.1.