MATH 314: Graph Theory
Syllabus
 Lecture
 196 Carver Hall
 TR 11:00am–12:15pm
 Office hours
 408C Carver Hall
 (These are tentative office hours until my schedule is finalized: valid through 01/24)
 M 11:00am–12:00pm
 R 1:00pm–3:00pm
 (Official office hours: starting 01/25)
 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 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  HW1  Solutions 
Jan 28  
February  
Feb 1  HW2  Solutions  
Feb 3  Discussion session #1  DS1 
Feb 8  HW3  Solutions  
Feb 10  
Feb 15  HW4  Solutions  
Feb 17  Discussion session #2  DS2 
Feb 22  HW5  Solutions  
Feb 24  
March  
Mar 1  HW6  Solutions  
Mar 3  
Mar 8  Review day, Discussion session #3  DS3 
Mar 10 


Mar 15  No Class (Spring Break)  
Mar 17  
Mar 22  HW7  Solutions  
Mar 24  
Mar 29  HW8  Solutions  
Mar 31  
April  
Apr 5  HW9  Solutions  
Apr 7  Discussion session #4  DS4 
Apr 12  HW10  Solutions  
Apr 14  
Apr 19  HW11  Solutions  
Apr 21  Discussion session #5  DS5 
Apr 26  HW12  Solutions  
Apr 28  
May  
May 3  HW13  Solutions  
May 5  Review day, Discussion session #6  DS6 
TBA 


Quick notation
This list will grow throughout the semester.
Notation  Meaning 

$[n]$  $\{1,\dots,n\}$ 
$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$ 
$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$ 
$G[X]$ where $X\subseteq V(G)$  subgraph of $G$ induced by $X$ 
$G\cup H$ or $G\sqcup H$  disjoint union of $G$ and $H$ 
$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$ (nb: usually $\times$ denotes a different graph product known as the categorical product, so be careful when reading other texts) 
$d(u,v)$  distance between vertices $u$ and $v$ 
$\deg v$  degree of the vertex $v$ 
$\Delta(G)$  maximum degree of $G$ 
$\delta(G)$  minimum degree of $G$ 