Summer's here and I've had the luxury to just play around. I try to put extra math into the curriculum through either warm up problems, extra credit problems, or examples in the curriculum that I follow. Discrete math figures prominently in the extra math. In my opinion, discrete math deserves a prominent place in the high school curriculum; it certainly deserves a bigger share of the curriculum. But in a top down system you can't add extra material to the curriculum that the average math teacher has never seen and expect it to be implemented properly.
Graph theory is ideal because it requires little mathematical background to understand and solve problems yet it also provides a way to introduce theorems (many of a basic nature that high school students can understand) along with counterexamples thereby providing a basic primer into the sort of considerations that mathematicians are looking at. In the past, geometry had been the topic for introducing proofs but it's dry as dust and now common core has ripped out much of the proof content so that your typical student can go through math and with very limited exposure to theorems/proofs/counterexamples.
Graph theory would be a way to get that back in a way that is much more interesting than the dry "2 parallel lines are cut by a transversal" proofs that have bored generation after generation. You can even connect to matrices through the adjacency matrix of a graph. Topics like recurrence relations and generating functions complement the curriculum of calculus (power series) and probability. Unfortunately, common core has de-emphasized proofs and matrices and upped the exposure to statistics, so I think it's my duty to undue the damage of the curriculum.
Which brings us back to the current post. Bipartite graphs which have the same number of vertices in each partite set provide a way of determining whether a suitable job can be found for each person so that everyone has a job (see the "Matching" section for the link above). One partite set with vertices, say, A,B,C,D have edges to the other partite set of vertices (a,b,c,d) representing jobs based on whether the person is qualified to do the job. The question becomes, Is there an assignment of jobs so that everyone has a job they're qualified to do? If yes, then there is a (perfect) matching for the graph. If no then there needs to be an explanation as to why no such assignment is possible (Hall's Marriage Theorem).
As a teacher the problem I usually face is finding lots of examples that can be used in the classroom or on a test/quiz. Sage/sagetex is the tool that works best for me. The code generates bipartite graphs so that the number of vertices in each partite set is equal and the probability of an edge being selected for the picture is 1/2. The code is posted on the Graphics page along with sample output (the PDF shown above). The number of vertices is a random number set between 4 and 8 here: N = Integer(randint(4,8)). The probability of the edge being chosen is set here: if Integer(randint(0,1))==1:
It would be relatively simple to choose a larger number than 1, such as 9, and draw the edge if the number chosen is between 0 and 7 but don't draw the edge if the number chosen is 8 or 9. That would make the probability of the edge appearing to be 80%.
Through setting the parameters to your liking and repeatedly compiling the code you can generate many examples that you can use. If you're particularly ambitious you can add extra code spit out example that have (or fail to have) a perfect matching. Of course, Sage can help with that.