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 inperson 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, cutvertices, blocks, extra notes  
March  
Mar 1  Blocks (continued), vertexconnectivity, edgeconnectivity, extra notes  HW6 (.tex)  Solutions 
Mar 3  Vertex and edgeconnectivity (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 edgecovers, $\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, edgechromatic numbers, extra notes  HW10 (.tex)  Solutions 
Apr 14  Intro to planar graphs, Euler's formula, headshaking lemma, extra notes  
Apr 19  6color theorem, Kuratowski's Theorem (statement), Kempe swaps, 5color 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  Lowerbounds 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  powerset 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 coproduct 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$ 
$Gv$ where $v$ is a vertex of $G$  remove the vertex $v$ along with any incident edges from $G$ 
$Ge$ 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$ 
$GU$ 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 $Ge$... 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$  outdegree 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$  indegree 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)$  vertexconnectivity of $G$ 
$\lambda(G)$  edgeconnectivity of $G$ 
$\alpha(G)$  independence number of $G$ 
$\omega(G)$  clique number of $G$ 
$\alpha'(G)$  matching number/edgeindependence number of $G$, i.e. the largest matching in $G$ 
$\beta(G)$  vertexcover number of $G$, i.e. min number of vertices that touch all edges 
$\beta'(G)$  edgecover number of $G$, i.e. min number of edges that touch all vertices 
$\chi(G)$  chromatic number of $G$ 
$\chi'(G)$  edgechromatic 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,bluecoloring 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 casetocase), 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 casetocase). 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.