Math 412 Test 1 - Wednesday 02/26

List of topics

• Isomorphism of graphs.
• Representations of graphs: adjacency and incidence matrices.
• Walks, Path, Trails, cycles, walks trails, Lemma 1.2.15 in the book, Lemma 1.2.25, Proposition 1.2.27, Eulerian circuits and trails. Euler's Theorem (1.2.26).
• Bipartite graphs. A characterization of bipartite graphs (Theorem 1.2.18).
• Extremal problems on graphs. Mantel's Theorem (1.3.23), Turán's theorem (5.2.9)
• Graphic sequences. Havel-Hakimi (Theorem 1.3.31)
• Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs (Theorem 1.4.26).
• Tournaments, kings in tournaments (Proposition 1.4.30).
• Trees, characterizations of trees (Theorem 2.1.4, Corollary 2.1.5).
• Distances in graphs. Centers of trees (Theorem 2.1.3).