Included below are the definitions, notation, and proposition statements presented in each day's class. Propositions which can be found in Diestel's book are indicated by their number in the 3rd edition.
Basics
Class 1:
Definitions: Graph, vertices, edges, adjacent, neighborhood, independent set, subgraph, induced subgraph, degree, regular graph.
Definitions: N(v) the neighborhood of a vertex v, G[X] the induced subgraph of G on a subset X of vertices, G-X the subgraph G[V\X] for a subset X of vertices, G-U the subgraph (V(G), E(G) \ U) for a subset U of edges, deg(v) the degree of a vertex v, δ(G) the minimum degree in a graph G, Δ(G) the maximum degree in a graph G.
Proposition: For every graph G, 2 |E(G)| = ∑v ∈ V(G) deg(v).
Definitions: Path, ends of a path, linked by a path, the length of a path, walk.
Proposition: If a graph G has a walk from vertices x to y, then there exists a path from x to y.
Definitions: Cycle, length of a cycle.
Proposition [1.3.1]: Every graph G has a path of length δ(G) and a cycle of length δ(G) + 1.
Definitions: Connectivity, component, separation.
Proposition: If C is a cycle in a connected graph G and e ∈ E(C), then G-e is connected.
Definitions: Tree, leaves of a tree, root of a tree, forest
Proposition [1.5.1]: The following are equivalent for a graph T
Class 2:
Proposition [1.5.3]: T a connected graph. Then T is a tree iff |E(T)| = |V(T)| -1.
Definitions: bipartite graph, bipartition of a bipartite graph.
Proposition: A graph G is bipartite iff every subgraph of G is bipartite.
Proposition [1.6.1]: A graph G is bipartite iff G has no odd cycle.
Definitions: The subpath xPy of a path P.
Definitions: Closed walk, Eulerian tour.
Proposition [1.8.1] (Euler 1736): Let G be a connected graph. Then G has an Eulerian tour iff every vertex has even degree.
Definitions: Hamiltonian cycle.
Proposition [10.1.1] (Dirac 1952): G a graph with n vertices and δ(G) ≥ n/2. Then G has a Hamiltonian cycle.
Structures in Graphs I: Matching
Class 3:
Definitions: matching, M-augmenting path, M-alternating path.
Proposition [Ch2, exercise 1]: G a graph and M a matching in G. Then there exists an M-augmenting path iff there exists a matching M' with |M| < |M'|.
Definitions: vertex cover.
Proposition [2.1.1] (Konig 1931): The maximum cardinality of a matching in a bipartite graph G is equal to the minimum cardinality of a vertex cover.
Definitions: Marriage condition.
Proposition [2.1.2] (Hall 1935): Let G be a bipartite graph with bipartition (A, B). Then G contains a matching covering A iff for all S ⊆ A, |N(S)| ≥ |S|.
Class 4:
Proposition: There exists a polynomial time algorithm which given a matching M in a bipartite graph G either finds an M-augmenting path or determines that no such augmenting path exists.
Discussion of Edmonds blossom algorithm.
Definitions: Stable matching.
Proposition [2.1.4] (Gale and Shipley 1962) For every choice of preferences, a bipartite graph G has a stable matching.
Class 5:
Definitions: Perfect matching.
Proposition [2.2.1] (Tutte 1947): Let G be a graph. G has a perfect matching iff for all S ⊆ V(G), G-S has at most |S| distinct components containing an odd number of vertices.
Class 6:
Definitions: Bridge.
Proposition [2.2.2] (Petersen 1891): Every cubic bridgeless graph has a perfect matching.
Proposition: Let G be a bipartite graph. Then the maximum size of a matching is equal to the minimum size of a vertex cover.
Structures in Graphs II: Packing
Definitions: A-B path, A-B cutset, A-B separation, order of an A-B separation, trivial A-B path.
Proposition: Let G be a graph and A, B subsets of vertices. For all k ≥ 0, there exists an A-B cutset of size k iff there exists an A-B separation of size k.
Proposition [3.3.1] (Menger 1927): Let G be a graph, k a non-negative integer, and A, B subsets of vertices. Then either there exists k disjoing A-B paths or there exists an A-B separation of order at most k-1.
Class 7:
Definitions: k-connected, internally disjoint paths.
Proposition [Ch3, exercise 17]: Let k be a positive integer. If G is k-connected, then for every pair of vertices x, y ∈ V(G), there exist k internally disjoint paths from x to y.
Definitions: subdivide an edge, subdivision, topological minor.
Proposition: Every 3-connected graph contains K4 as a topological minor.
Proposition: Let k be a positive integer. For every k-connected graph G and every choice of k vertices x1,..., xk there exists a cycle C of G containing all the vertices x1,..., xk.
Definitions: directed graph, directed path, path cover.
Proposition [2.5.1] (Gallai and Milgram 1960): Let G be a directed graph. Then there exists a path cover P1,..., Pk and an independent set {x1,..., xk} such that xi∈ Pi for all 1 ≤ i ≤ k.
Class 8:
Definitions: partially ordered set, poset, chain, anti-chain.
Proposition [2.5.2] (Dilworth 1950): For every poset P, the minimum number of chains whose union is P is equal to the maximum size of an antichain.
Proposition: Every 3-regular graph contains a cycle of length at most 2 times the ceiling of log |V(G)|
Proposition: There exists a constant c' such that if G is a 3-regular multigraph on at least c'k log k vertices, then there exist k vertex disjoint cycles in G.
Proposition: (Erdos-Posa, 1965) There exists a constant c such that for all graphs G, either G has k disjoint cycles or there exists a set X of vertices, |X| ≤ c k log k such that G-X has no cycle.
Structures in Graphs III: Extremal graph theory
Class 9:
Definitions: r-partite, complete r-partite.
Proposition: Let r be a positive integer. An (r-1)-partite graph does not contain Kr as a subgraph.
Definitions: Turan graph Tr(n), tr(n), edge maximum graph with no Kr, ex(n,Kr).
Proposition: Let G be a graph on n vertices which is edge maximum with no Kr subgraph. Assume G is (r-1)-partite. Then G=Tr-1(n).
Proposition [7.1.1] (Turan 1941): Let r > 1 and n be positive integers. Let G be a graph on n vertices which does not contain Kr as a subgraph and assume G has ex(n, Kr) edges. Then G = Tr-1(n).
Proposition: Let G be a graph on n vertices. If |E(G)| > tr-1(n), then G contains Kr as a subgraph.
Class 10:
Proposition [7.2.1] (Bollobas and Thomason 1996): There exists a constant c such that for all positive integers r the following holds. Let G be a graph with |E(G)| ≥ cr2|V(G)|. Then G contains Kr as a topological minor. (not proven in class)
Proposition [1.4.3] (Mader 1972): Let k be a positive integer. Every graph G with n ≥ 2k vertices and |E(G)| ≥ (2k-1)(n-k) contains a k-connected subgraph.
Proposition: Let k be a positive integer. Every graph with minimum degree at least 4k contains a k-connected subgraph.
Proposition: Every graph on n vertices with 5n edges contains K4 as a topological minor.
Definition: edge contraction, minor, e(G)
Proposition: For p ≤ 7, every graph G which satisfies e(G) > (p-2)n + N(p-1, 2) contains
Kp as a minor.
Definitions: Ramsey number R(t).
Proposition: R(1) = 1, R(2) = 2, R(3) = 6.
Proposition [9.1.1] (Ramsey 1930): For every t ≥ 1, the value R(t) exists and R(t) ≤ 22t-3.
Class 11:
Definitions: Complement of G, R(s, t).
Proposition: R(3,4) ≤ 9.
Proposition: R(4) ≤ 18.
Global Properties I: Graph Decompositions
Definitions: block
Proposition: Blocks overlap in at most one vertex, and if they intersect, they intersect in a cut vertex of the graph.
Definition: block graph.
Proposition [3.1.2]: The block graph of a connected graph is a tree.
Definition: H-path, ear decomposition.
Proposition [3.1.3]: A graph G is 2-connected if and only if G has an ear decomposition.
Class 13:
Proposition [3.2.1]: If G is 3-connected and |V(G)| > 4, then there exists an edge e such that G/e is 3-connected.
Proposition [3.2.2] (Tutte 1961): A graph G is 3-connected if and only if there exists a sequence G0, G1, ..., Gn of graphs such that
1. G0 = K4 and Gn = G.
2. Gi has an edge xy with deg(x), deg(y) ≥ 3 and Gi = Gi+1 /xy for all i < n.
Global Properties II: Planar Graphs
Definitions: straight line segment, polygon, polygonal arc, links, interior int(P) of a polygonal arc P, regions, separates, frontier.
Proposition [4.1.1] (Jordan curve theorem): For every polygon P in ℜ2, the set ℜ2 - P has exactly 2 regions. Each of these regions has the entire polygon as it's boundary. (not proven in class)
Proposition [4.1.2]: Let P1, P2, P3 be 3 polygonal arcs from the same 2 endpoints, but otherwise disjoint.
1. ℜ2 - (P ∪ P ∪ P) has exactly 3 regions with frontiers P1 ∪ P2, P1 ∪ P3, P2 ∪ P3.
2. If P is an arc between a point in int(P1) and int(P2) whose interior lies in the region of ℜ2- (P1 ∪ P2) containing int(P3), then P ∩ P3 ≠ ∅. (not proven in class)
Proposition [4.1.3]: Let X1, X2 ⊆ ℜ2 be disjoint sets each made up of the union of finitely many points and straight line segments and let P be an arc between a point in X1 and X2 such that int(P) ⊆ region O of ℜ2 - (X1 ∪ X2). Then O - int(P) is a region of ℜ2 - (X1 ∪ X2 ∪ P). (not proven in class)
Class 14:
Definitions: plane graph, faces, outer face, inner face.
Proposition [4.2.1]: Let G be a plane graph, f a face of G, and H a subgraph of G. Then:
1. H has a face f' containing f.
2. If the frontier of f lies in H, then f = f'.
Proposition [4.2.4]: A plane forest T has exactly one face.
Proposition [4.2.2]: Let G be a plane graph and e an edge of G.
1. If X is the frontier of a face, then either e ⊆ X or e ∩ X = ∅.
2. If e lies on a cycle C ⊆ G, then e lies on the frontier of exactly two faces of G and these are contained in distinct faces of C.
3. If e lies on no cycles, then e lies on the frontier of exactly one face of G.
Definitions: boundary of a face
Proposition [4.2.5]: If a plane graph has different faces with the same boundary, then the graph is a cycle.
Proposition [4.2.6]: In a 2-connected graph, every face is bounded by a cycle.
Class 15:
Definitions: induced cycle.
Proposition [4.2.7]: Let G be a 3-connected plane graph and let C be a subgraph of G. Then C is a face boundary if and only if C is a non-separating induced cycle.
Definitions: maximally plane.
Proposition [4.2.8]: A plane graph G, |V(G)| ≥ 3, is maximally plane if and only if every face is a triangle.
Proposition [4.2.9] (Euler): Let G be a connected plane graph with n vertices, m edges, and f faces. Then n-m+f = 2.
Definitions: triangulation.
Proposition [4.2.10]: A plane graph with n ≥ 3 vertices has at most 3n-6 edges and every plane triangulation has 3n-6 edges.
Definitions: planar.
Proposition: K5 is not planar.
Proposition: A bipartite plane graph on n ≥ 2 vertices has at most 2n-4 edges.
Proposition: K3,3 is not planar.
Proposition: If H is not planar, then every subdivision of H is not planar.
Proposition [4.2.11]: If G is planar, then G does not contain as a topological minor K5 or K3,3.
Class 16:
Proposition [4.4.6] (Kuratowski 1930): A graph G is planar if and only if G does not contain K5 or K3,3 as a topological minor. (not proven in class)
Definitions: minor.
Proposition: G contains a graph H as a minor if and only if there exist sets {Xv : v ∈ V(H)} such that
Proposition: G contains H as a topological minor implies G contains H as a minor.
Proposition [4.4.2]: G contains K5 or K3,3 as a topological minor if and only if G contains K5 or K3,3 as a minor.
Proposition: If H is 3-regular, then G contains H as a topological minor if and only if G contains H as a minor.
Proposition [4.4.3]: If G is 3-connected, then G is planar if and only if G does not contain K5 or K3,3 as a minor.
Global Properties III: Graph Coloring
Class 17:
Definitions: k-coloring, chromatic number.
Proposition: A graph G has chromatic number 2 if and only if G is bipartite.
Proposition: Every graph G is Δ(G) + 1 colorable.
Proposition: Every planar graph is 4-colorable. (not proven in class)
Proposition: Every planar graph is 6-colorable.
Proposition [5.1.2]: Every planar graph is 5-colorable.
Class 18:
Proposition [5.2.4] (Brooks 1941): Let G be a connected graph. If G is neither an odd cycle nor a clique, then the chromatic number of G is at most Δ(G).
Definitions: ω(G).
Proposition: The chromatic number of G is at least ω(G).
Class 19:
Proposition: There exist graphs Gn for all positive integers n which do not contain K3 as a subgraph such that the chromatic number of G is at least n.
Definitions: perfect graph.
Proposition: Bipartite graphs are perfect.
Definitions: chord, chordal graph.
Proposition [5.5.2]: Chordal graphs are perfect.
Definitions: interval graphs.
Proposition: Interval graphs are perfect.
Proposition: Both odd cycles and the complements of odd cycles are not perfect.
Proposition [5.5.3] (Chudnovsky, Robertson, Seymour, Thomas 2002): A graph is perfect if and only if it does not contain as an induced subgraph either an induced odd cycle or an induced complement of an odd cycle. (not proven in class)