**chapter 4Binary Relations and Inductive Proof**

*Good order is the foundation of all things*.

—Edmund Burke (1729–1797)

Classifying and ordering things are activities in which we all engage from time to time. Whenever we classify or order a set of things, we usually compare them in some way. That’s how binary relations enter the picture. In this chapter, we’ll discuss some of the desired properties of binary relations that are useful for solving problems.

We’ll learn how to construct new binary relations that can be used to solve path problems in graphs. We’ll see how the idea of equivalence is closely related to partitioning of sets, as well as how the results are applied in an algorithm to find a minimal spanning tree for a graph. We’ll also ...