He offered a bet that we could name any person among earth’s one and a half billion inhabitants and through at most five acquaintances, one of which he knew personally, he could link to the chosen one.
— Frigyes Karinthy, Láncszemek1
The following presentation is loosely based on the first chapters of Graph Theory by Reinhard Diestel and Digraphs by Bang-Jensen and Gutin, and on the appendixes of Introduction to Algorithms by Cormen et al. (Note that the terminology and notation may differ between books; it is not completely standardized.) If you think it seems like there’s a lot to remember and understand, you probably ...