MATH 314: Graph Theory
Syllabus
- Lecture
- 196 Carver Hall
- TR 11:00am–12:15pm
- Office hours
- 408C Carver Hall
- M 12:00pm–1:00pm
- R 2:00pm–4:00pm
- Textbook
- 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.
| January | ||
| 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 | |
| February | ||
| 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 | |
| March | ||
| 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 |
|
|
| 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 | |
| April | ||
| 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 | ||
| 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 |
|
|
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.