Fall 2004 Math 412 Graph Theory sections G1U and G1G

Test 1 Material

These are the major topics to be covered on the first test. Most topics require foundational and background knowledge.

1. Bipartite graphs. A characterization of bipartite graphs.

2. Isomorphism of graphs.

3. Representations of graphs: adjacency and incidence matrices.

4. Eulerian circuits and trails. Euler Theorem.

5. Extremal problems on graphs. Mantel's Theorem.

6. Graphic sequences. A theorem on such sequences.

7. Directed graphs: degrees, connectivity, Eulerian circuits, de Bruijn graphs.

8. Tournaments, kings in tournaments.

9. Trees, characterizations of trees.

10. Centers of trees.

11. Prufer codes, Cayley's formula.

    Back This page last modified .