MATH 314: Graph Theory


196 Carver Hall
TR 11:00am–12:15pm
Office hours
408C Carver Hall
M 12:00pm–1:00pm
R 2:00pm–4:00pm
A first course in graph theory by Gary Chartrand and Ping Zhang
Other materials will be distributed as necessary

Schedule and Assignments

Homework assignments are due by the end of lecture on the date by which they are posted. If you cannot attend class when an assignment is due, you are responsible for emailing your assignment to me: this email must be in my inbox by the end of lecture, and your submission must be a .pdf file. Late submissions (be they submitted in-person or by email) incur a 1% (as in percentage point) penalty per minute of being late, e.g. an assignment submitted at 12:27pm which would have received an 80% will instead receive a 68%.

If you email your homework to me, please include "MATH 314" and the homework number in the subject line. This will help me ensure I don't miss any submissions.

If you wish to write your assignments in $\LaTeX$, here's a basic homework template you can use.

A note on pictures and proofs

Oftentimes it is tempting to use a sketch of a graph (or some piece of a graph) as a part of your proof. While sketches can be very helpful in understanding a problem and reasoning through its solution, sketches can be misleading and generally should not be included in a proof. Unless explicitly requested by a problem, none of your proofs should include sketches.

Jan 18 Basic definitions and important jargon, walks, paths, cycles, connectivity, extra notes
Jan 20 Connectivity (continued), bipartite graphs, extra notes
Jan 25 Special graphs, complements, friends of graphs, vertex degrees, handshaking lemma, extra notes HW1 (.tex) | Solutions
Jan 27 Degrees and connectivity, regular graphs, extra notes
Feb 1 Degree sequences, Havel–Hakimi Theorem, Erdős–Gallai Theorem (one direction), extra notes HW2 (.tex) | Solutions
Feb 3 Graph isomorphisms and automorphisms, Discussion session #1 DS1 | Solution sketches
Feb 8 Introduction to trees, extra notes HW3 (.tex) | Solutions
Feb 10 More about trees and forests, spanning trees, extra notes
Feb 15 Minimum spanning trees, Kruskal's algorithm, Prim's algorithm HW4 (.tex) | Solutions
Feb 17 Trees are everywhere, Discussion session #2 DS2 | Solution sketches
Feb 22 Enumerating trees using Prüfer codes (this topic is not in the book), notes, supplementary notes HW5 (.tex) | Solutions
Feb 24 Connectivity revisited, cut-vertices, blocks, extra notes
Mar 1 Blocks (continued), vertex-connectivity, edge-connectivity, extra notes HW6 (.tex) | Solutions
Mar 3 Vertex- and edge-connectivity (continued), Menger's Theorem, extra notes
Mar 8 Review day, Discussion session #3 DS3 | Solution sketches
Mar 10
You may bring one standard 8.5x11 sheet of paper with handwritten notes.
All materials through HW6 are fair game. Beyond those materials, you may be required to know what cut-vertices are and prove some basic properties about them, but you will not be explicitly tested on block decompositions, vertex/edge connectivity or Menger's theorem.
Mar 15 No Class (Spring Break), extra fun if you're bored
Mar 17
Mar 22 Eulerian circuits and trails, extra notes HW7 (.tex) | Solutions
Mar 24 Hamilton cycles and paths
Mar 29 Matchings, vertex- and edge-covers, $\alpha,\alpha',\beta,\beta'$, Kőnig's Theorem, extra notes HW8 (.tex) | Solutions
Mar 31 Hall's Marriage Theorem, extensions and applications, extra notes, supplementary notes
Apr 5 Graph colorings, chromatic numbers, extra notes HW9 (.tex) | Solutions
Apr 7 $\chi(G)$ vs $\chi(\overline{G})$, Discussion session #4, extra notes DS4 | Solution sketches
Apr 12 Chromatic numbers and trees, edge-chromatic numbers, extra notes HW10 (.tex) | Solutions
Apr 14 Intro to planar graphs, Euler's formula, headshaking lemma, extra notes
Apr 19 6-color theorem, Kuratowski's Theorem (statement), Kempe swaps, 5-color theorem, extra notes HW11 (.tex) | Solutions
Apr 21 Discussion session #5 DS5 | Solution sketches
Apr 26 Introduction to Ramsey numbers, extra notes HW12 (.tex) | Solutions
Apr 28 Lower-bounds on Ramsey numbers, how many monochromatic triangles are there?, extra notes
May 3 Extremal numbers, Mantel, Turán, Kővári–Sós–Turán (special case), extra notes HW13 (.tex) | Solutions
May 5 Review day, Discussion session #6 DS6 | Solution sketches
May 12
Final Exam
You may bring one standard 8.5x11 sheet of paper with handwritten notes.
The exam will focus on materials covered in HW7–HW13. Of course, this class builds heavily upon itself, so you won't succeed in this exam unless you have a firm grasp on the materials in HW1–HW6.
Location & Time
196 Carver Hall
Thursday, May 12

Quick notation

This list will grow throughout the semester.

Notation Meaning
$[n]$ $\{1,\dots,n\}$ (Note: $[0]=\varnothing$)
$2^X$ where $X$ is a set power-set of $X$ (nb: if $X$ is finite, then $|2^X|=2^{|X|}$)
${X\choose k}$ where $X$ is a set $\{S\in 2^X:|S|=k\}$ (nb: if $X$ is finite, then $|{X\choose k}|={|X|\choose k}$)
$A\sqcup B$ disjoint union of sets $A$ and $B$ (Note: this is identical to the standard union of sets, but we use it to enforce the idea that $A$ and $B$ are disjoint for the sake of brevity. That is to say, $A\sqcup B$ makes sense iff $A$ and $B$ are disjoint. If $A$ and $B$ aren't disjoint, but one still wants to treat them as such when taking their "union", there's a notion known as the co-product of sets, denoted by $A\amalg B$, but we won't use that in this class.)
$V(G)$ vertex set of $G$
$E(G)$ edge set of $G$
$K_n$ clique on $n$ vertices
$C_n$ cycle on $n$ vertices
$P_n$ path on $n$ vertices
$K_{m,n}$ complete bipartite graph with parts of sizes $m$ and $n$
$K_{n_1,n_2,\dots,n_t}$ complete $t$-partite graph with parts of sizes $n_1,n_2,\dots,n_t$
$\overline{G}$ complement of $G$
$G-v$ where $v$ is a vertex of $G$ remove the vertex $v$ along with any incident edges from $G$
$G-e$ where $e$ is an edge of $G$ remove the edge $e$ from $G$, but keep all vertices
$G+e$ where $e$ is an edge not in $G$ add the edge $e$ to $G$
$G-U$ where $U$ is either a set of vertices or a set of edges of $G$ If $U$ is a set of vertices, delete each of them from $G$ along with any incident edges. If $U$ is a set of edges, delete each of them from $G$ but keep all vertices. This notation is somewhat ambiguous since an edge $e$ is a set of vertices, so it conflicts with the earlier notation of $G-e$... In other words, context is necessary when using this notation.
$G[X]$ where $X\subseteq V(G)$ subgraph of $G$ induced by $X$ (Note: $G[X]=G-(V(G)\setminus X)$)
$L(G)$ the line graph of $G$
$G\cup H$ or $G\sqcup H$ disjoint union of $G$ and $H$ (Note: I will always use $\sqcup$ since it reinforces the disjointness)
$G+H$ or $G\vee H$ join of $G$ and $H$
$G\mathbin\square H$ or $G\times H$ Cartesian product of $G$ and $H$ (Note: Usually $\times$ denotes a different graph product known as the categorical product, so be careful when reading other texts. I will always use $\square$.)
$d(u,v)$ distance between vertices $u$ and $v$
$N(v)$ neighborhood of $v$
$\deg v$ degree of the vertex $v$
$\Delta(G)$ maximum degree of $G$
$\delta(G)$ minimum degree of $G$
$\deg^+ v$ or $\operatorname{od}v$ out-degree of the vertex $v$ in a digraph (Note: I will never use $\operatorname{od}$ since that's just dumb)
$\deg^- v$ or $\operatorname{id}v$ in-degree of the vertex $v$ in a digraph (Note: I will never use $\operatorname{id}$ since that's just dumb)
$G\cong H$ $G$ and $H$ are isomorphic graphs
$\operatorname{Aut}(G)$ automorphism group of $G$
$\kappa(G)$ vertex-connectivity of $G$
$\lambda(G)$ edge-connectivity of $G$
$\alpha(G)$ independence number of $G$
$\omega(G)$ clique number of $G$
$\alpha'(G)$ matching number/edge-independence number of $G$, i.e. the largest matching in $G$
$\beta(G)$ vertex-cover number of $G$, i.e. min number of vertices that touch all edges
$\beta'(G)$ edge-cover number of $G$, i.e. min number of edges that touch all vertices
$\chi(G)$ chromatic number of $G$
$\chi'(G)$ edge-chromatic number/chromatic index of $G$, i.e. chromatic number of $L(G)$
$R(m,n)$ The Ramsey number of $K_m$ vs $K_n$, i.e. the smallest integer $N$ such that any red,blue-coloring of $E(K_N)$ contains either a red copy of $K_m$ or a blue copy of $K_n$

This is a general notational trend in graph theory. If, say, $\zeta(G)$ is some parameter of $G$ which is defined based mainly on the vertices of $G$ (what exactly this means varies from case-to-case), then generally $\zeta'(G)$ is the analogous parameter of $G$ defined based mainly on the edges of $G$ (again, what exactly this means varies from case-to-case). Sometimes $\zeta'(G)=\zeta(L(G))$, e.g. $\alpha$ vs $\alpha'$, but not always, e.g. $\beta$ vs $\beta'$. Also, this trend is broken often enough, e.g. $\kappa$ vs $\lambda$, but it is common enough to point out.