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 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 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
Midterm
The exam will cover all materials through HW6
You may bring one standard 8.5x11 sheet of paper with handwritten notes
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
Final Exam
The exam will focus on materials covered in HW6–HW13
You may bring one standard 8.5x11 sheet of paper with handwritten notes
Location & Time
TBA

Quick notation

This list will grow throughout the semester.

Notation Meaning
$[n]$ $\{1,\dots,n\}$
$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$
$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[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$