Math 412 Test 1 - Tuesday 02/16

A good way to study for the exam is to go through old homework problems, including the suggested problems.

List of topics - you should be familiar with the following topics and at least the main ideas behind all of the proofs.

• graphs, simple graphs, independent sets, cliques, complement, Isomorphism of graphs, self-complementary graphs, decompositions
• Representations of graphs: adjacency and incidence matrices.
• strong induction, connectivity, cut-edges, cut-vertices, 1.2.5, 1.2.11, 1.2.14, 1.3.15
• Walks, Path, Trails, cycles, trails, Lemma 1.2.15 in the book, Lemma 1.2.25, Proposition 1.2.27, Eulerian circuits and trails, theorem on Eulerian circuits (1.2.26).
• Bipartite graphs. A characterization of bipartite graphs Konig's Theorem (Theorem 1.2.18),
• Degree sum formula 1.3.3, 1.3.4, 1.3.5 and 1.3.9
• Definition of the hypercube
• Extremal problems on graphs. 1.3.13, 1.3.19, Mantel's Theorem (1.3.23)
• Graphic sequences. Havel-Hakimi (Theorem 1.3.31)
• Directed graphs: degrees, connectivity, adjacency and incidence matrices, Eulerian circuits, de Brujin graphs (Theorem 1.4.26).
• Tournaments, kings in tournaments (Proposition 1.4.30).