Wednesday April 9

We went back through the proof that subgraphs of bipartite graphs are bipartite.
The main point to absorb here was that
to show something exists (here, a splitting of the subgraph),
the best thing to do is EXHIBIT an example.
This isn't always how it works; there are a very few "pure existence" proofs that don't actually construct an example. But they are very rare, and your first impulse should be to find a recipe for an example.

Here's an example I didn't give in class:
Theorem. For any real number x, there exists a real number y such that x < y < x+1.
Proof. Let y = x + 1/37. Then y satisfies the desired properties. QED.

Note that lots of other recipes would have worked just as well -- we only needed one.

Then we defined circuits in graphs, and headed toward the theorem that circuits in bipartite graphs are always of even length. (Someday we'll prove a converse to this.)