# 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$