Discrete Mathematics: Elementary and Beyond

10.4 How to Find a Perfect Matching 171 a b k k-1 FIGURE 10.5. Goodness lost when two nodes are removed For the second graph, it ...

172 10. Matchings in Graphs We may assume that|A|=|B|(where, as before,Ais the set of nodes on the left andBis the set of nodes ...

10.4 How to Find a Perfect Matching 173 10.4.1Show by an example that it may happen that a bipartite graphGhas a perfect matchin ...

174 10. Matchings in Graphs If we find an augmenting pathP, we can delete those edges ofPthat are inMand replace them by those e ...

10.4 How to Find a Perfect Matching 175 T UW r? r? S s q FIGURE 10.7. Reaching nodes by almost augmenting paths. Only edges on t ...

176 10. Matchings in Graphs (a) (c) (d) (b) FIGURE 10.8. (a) The graph in which we want to find a perfect matching. (b) Pick a s ...

10.4 How to Find a Perfect Matching 177 FIGURE 10.9. A graph for trying out the algorithm. 10.4.8Now suppose that we have the we ...

178 10. Matchings in Graphs 10.4.12 Draw a graph whose nodes are the 2-subsets of{a, b, c, d, e}, and two nodes are adjacent if ...

11 Combinatorics in Geometry 11.1 Intersections of Diagonals At first you may be surprised: What is the connection between combi ...

180 11. Combinatorics in Geometry The first natural idea to solve this problem is the following: Count the intersection points o ...

11.2 Counting regions 181

  A B C D E F ABEF ACDE FIGURE 11.3. Now if we want to count all the intersection points, it s ...

182 11. Combinatorics in Geometry parallel and no three going through the same point, then you invariably get 11 regions. In fac ...

11.2 Counting regions 183 We are not done yet; what does this give for the number of regions? We start with 1 region for 0 lines ...

184 11. Combinatorics in Geometry edge of the blackboard tilts a little to the left (else, we tilt the blackboard by a tiny amou ...

11.3 Convex Polygons 185 In the sequel, for the sake of brevity we will say that certain points are ingeneral position, if no th ...

186 11. Combinatorics in Geometry A D E B C FIGURE 11.9. Finding a convex quadrilateral. points with this property, and in fact ...

11.3 Convex Polygons 187 11.3.3Into how many parts do two triangles divide the plane? 11.3.4Into how many parts do two quadrilat ...

This page intentionally left blank ...

12 Euler’s Formula 12.1 A Planet Under Attack In Chapter 11 we considered problems that can be cast in the language of graph the ...

190 12. Euler’s Formula boundaries between countries but as dams, with watchtowers at the nodes. So the enclosed areas are not c ...