Graph Theory

Graph Theory

Professor:

Paul Wollan

Office Hours:

Class Times:

Announcements

There will be no class on Friday, March 15 and no class the week of 18 - 22 March.

Prerequisites:

The course requires a minimal acquaintance with combinatorics and discrete mathematics and the proof techniques used therein, primarily, mathematical induction. All other necessary background will be covered in the course itself. Description:

Graph theory has proven to be a rich and elegant field of discrete mathematics. In recent years, graph theory has also yielded numerous applications in discrete mathematics and theoretical computer science. The course covers the classic results and subtopics in the field as well as providing an introduction to current areas of research. The general topics covered in the course are:

Basic Concepts:

Graph Structures:

Graph Properties:

Recommended texts:

Graph Theory, Reinhard Diestel, 3rd edition, Springer Verlag 2005
Modern Graph Theory, Bela Bollobas, Springer Verlag 1991

Suggested problems to prepare for the exam:

Problems from Diestel's Graph Theory (pdf)

Class summaries

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 for a subset X of vertices, 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

T is a tree
Every pair of vertices is connected by a unique path
T is minimally connected
T is maximally acyclic

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.

Definitions: Bridge.

Proposition [2.2.2] (Petersen 1891): Every cubic bridgeless graph has a perfect matching.

Structures in Graphs II: Packing

Class 6:

Proposition: Let G be a bipartite graph. Then the maximum size of a matching is equal to the minimum size of a vertex cover.

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 K₄ as a topological minor.

Proposition: Let k be a positive integer. For every k-connected graph G and every choice of k vertices x₁,..., x_k there exists a cycle C of G containing all the vertices x₁,..., x_k.

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 P₁,..., P_k and an independent set {x₁,..., x_k} such that x_i ∈ P_i 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 K_r as a subgraph.

Definitions: Turan graph T_r(n), t_r(n), edge maximum graph with no K_r, ex(n,K_r).

Proposition: Let G be a graph on n vertices which is edge maximum with no K_r subgraph. Assume G is (r-1)-partite. Then G=T_r-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 K_r as a subgraph and assume G has ex(n, K_r) edges. Then G = T_r-1(n).

Proposition: Let G be a graph on n vertices. If |E(G)| > t_r-1(n), then G contains K_r 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)| ≥ cr²|V(G)|. Then G contains K_r 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 K₄ 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 K_p 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) ≤ 2^2t-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 G₀, G₁, ..., G_n of graphs such that

G₀ = K₄ and G_n = G.
G_i has an edge xy with deg(x), deg(y) ≥ 3 and G_i = G_i+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 R², the set R² - 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 P₁, P₂, P₃ be 3 polygonal arcs from the same 2 endpoints, but otherwise disjoint.

R² - (P₁ ∪ P₂ ∪ P₃) has exactly 3 regions with frontiers P₁ ∪ P₂, P₁ ∪ P₃, P₂ ∪ P₃.
If P is an arc between a point in int(P₁) and int(P₂) whose interior lies in the region of R²- (P₁ ∪ P₂) containing int(P₃), then P ∩ P₃ ≠ ∅. (not proven in class)

Proposition [4.1.3]: Let X₁, X₂ ⊆ R² 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 X₁ and X₂ such that int(P) ⊆ region O of R² - (X₁ ∪ X₂). Then O - int(P) is a region of R² - (X₁ ∪ X₂ ∪ 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:

H has a face f' containing f.
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.

If X is the frontier of a face, then either e ⊆ X or e ∩ X = ∅.
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.
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: K₅ is not planar.

Proposition: A bipartite plane graph on n ≥ 2 vertices has at most 2n - 4 edges.

Proposition: K_3,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 K₅ or K_3,3.

Class 16:

Proposition [4.4.6] (Kuratowski 1930): A graph G is planar if and only if G does not contain K₅ or K_3,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 {X_v : v ∈ V(H)} such that

X_u ∩ X_v = ∅.
G[X_u] is a connected subgraph of G for all u ∈ V(H).
For all uv ∈ E(H), there exists an edge from X_u to X_v in G.

Proposition: G contains H as a topological minor implies G contains H as a minor.

Proposition [4.4.2]: G contains K₅ or K_3,3 as a topological minor if and only if G contains K₅ or K_3,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 K₅ or K_3,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 G_n for all positive integers n which do not contain K₃ 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)