Graph Theory, Lecture 5: More on Trees, bipartite graphs, notion of minors

1-line proof that connected graphs with n vertices and n-1 edges are trees.
Shorter, inductive, proof of existence of normal spanning trees:
another example where strengthening the inductive statement helps.
Bipartite graphs (from 14:30), with first example of a 'good characterisation',
one that shows a decision problem to be in both NP and coNP (just after 36:55).
Notions of minor and topological minor (from 30:50), and of
directed graphs, oriented graphs, and multigraphs (from 1:17).
Covers rest of Chapter 1.5, Chapter 1.6-7, and Chapter 1.10.