Example 1 Joe the plumber has made an interesting offer. He says he has lots of short pieces of varying gauges of copper pipe; they are nearly worthless to him, but for only 1/5 of the usual cost of installing a plumbing connection under your house, he will use a bunch of T- and Y-joints he picked up at a distress sale and these small pipes to build the network shown in Figure 1. He claims that it will deliver three gallons per minute at maximum flow. He has a good reputation, so you are sure the network he builds will not leak and will cost what he promises, but he is no mathematician. Will the network really deliver as much water per minute as he claims?

Example 2 We want to block access to the sea from inland town s on river R. We can do this by dropping mines in the river, but because the river spreads out in a wide delta with several outlets, the number of mines required depends on where we drop them. The number of mines required in a channel ranges from a high of 20 mines in R to a low of 1 in some channels, as shown in Figure 2. In that ?gure, each channel is shown with a number indicating how many mines will block it. What is the smallest number of mines needed to block off s's access to the sea, and where should the mines be placed?

Example 3: At Major University, Professor Johnson is asked to hire graders for 100 sections spread among 30 different courses. Each grader may work for one, two, or three sections, with the upper bound being the grader's choice, but the number actually assigned being Professor Johnson's choice. Professor Johnson contacts the potential graders, learns from each both his choice of number of sections and which courses he is competent to grade, and makes a table showing this information, together with the number of sections of each course being offered. Because the real problem is too large to use as an example here, Table 1 gives a smaller example. How should the assignment of graders be made?