Midterm 1 Study Guide

Chapters covered: 1-4

1. Definition of a graph, order, size (1.1)
2. Neighbors, incident, adjacent (1.2)
3. Subgraphs, induced, spanning (1.2)
4. Walks, trails, paths, circuits, cycles (1.2)
5. Connected graphs, distance, geodesics, diameter (1.2)
6. Path graphs, Cycle graphs, complete graphs, bipartite graphs (1.3)
7. Proof that complement of a disconnected graph is connected, theorem 1.11 (1.3)
8. Know that a non-trivial graph is bipartite if and only if it contains no odd cycles, theorem 1.12 (1.3)
9. Cartesian product and join of graphs, \(n\)-cubes (1.3)
10. Degree of a vertex, \(\delta(G)\), \(\Delta(G)\). (1.3)
11. State the first theorem of graph theory and explain why it’s true (1.3)
12. Problems similar to example 2.2
13. Proof that every graph has an even number of odd vertices, corollary 2.3 (2.1)
14. Know theorem 2.4 (no proof)
15. Regular graphs (2.2)
16. Proof that if there is an \(r\)-regular graph of order \(n\), then \(0\leq r \leq n-1\) and at least one of \(r\), \(n\) is even (2.2)
17. Degree sequences (2.3)
18. Theorem 2.10 and its proof. Also know how to use the theorem to reconstruct a graph for a given sequence (2.3)
19. Definition of graph isomorphism, ways to show two graphs are not isomorphic (3.1)
20. Bridges. Proof that an edge is a bridge if and only if it lies on no cycle of the graph (4.1)
21. Acyclic graphs, forests, trees (4.2)
22. Proof that a graph is a tree iff any two vertices are connected by a unique path, theorem 4.2 (4.2)
23. Proof that every nontrivial tree contains at least two end-vertices, theorem 4.3 (4.2)
24. Proof that every tree has size equal to the order minus 1, theorem 4.4 (4.2)
25. Statement of corollary 4.6 (4.2)
26. Statement of theorem 4.8 (4.2)
27. Minimum spanning tree problem, describe and apply Kruskal’s and Prim’s algorithms (4.3)

Practice problems:

1. 1.15, 1.17, 1.22, 1.25,
2. 2.5, 2.6, 2.7, 2.14, 2.19, 2.26, 2.31, 2.32, 2.36
3. 3.1, 3.2, 3.4, 3.9, 3.16
4. 4.1, 4.2, 4.9, 4.11, 4.14, 4.17, 4.23, 4.27