\documentclass[a4paper]{book} \usepackage{amsmath, amsfonts,times,amsthm} \theoremstyle{plain} \newtheorem{proposition}{Proposition}[chapter] \newtheorem{theorem}[proposition]{Theorem} \newtheorem{corollary}[proposition]{Corollary} \newtheorem{observation}[proposition]{Observation} \newtheorem{definition}[proposition]{Definition} \newtheorem{example}[proposition]{Example} \newtheorem{lemma}[proposition]{Lemma} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\union}{\bigcup} \newcommand{\intersect}{\cap} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \begin{document} \frontmatter \title{Graph Theory} \date{Mich{\ae}lmas 2003} \maketitle \tableofcontents \mainmatter \chapter{Introduction} The notes were typed up by me, John Fremlin \texttt{john@fremlin.de}. These notes are based on the part IIA mathematics course ``Graph theory'' given by Dr Fisher in Cambridge in Mich{\ae}lmas 2003. These notes are not connected to Dr Fisher in any way. If there are any mistakes in them, it is more than very likely that they are my fault. I added a few clumsy elucidations, to the arguments that I initially did not understand, which will no doubt ensure that there are at least some errors, because I could not find any in Dr Fisher's lectures. Furthermore these notes are very definitely no substitute for actually going to lectures, because they do not include all of the material and especially examples covered, or any of the asides. Finally, I would like to thank Dr Fisher for his supervisions, where he taught me a lot about mathematics. \chapter{Graphs} % 20031013 (1) \begin{definition}[Graph] A graph is a pair $(V,E)$ with $E \subseteq V^{(2)}$. Loops and multiple edges are forbidden. \end{definition} \begin{definition}[Vertices] $V=V(G)$ is the set of vertices of $G$. \end{definition} \begin{definition}[Edges] $E=E(G)$ is the set of edges of $G$. \end{definition} \begin{example}[Complete graph] $K_n$ is the complete graph on $n$ vertices (all ${n \choose 2}$ edges). \end{example} \begin{example}[Cycle] $C_n$,$n \ge 3$ is a cycle of length $n$; it has vertices $v_1, v_2, \cdots, v_n$ and edges $v_1v_2, v_2v_3, \cdots$. \end{example} \begin{definition}[Isomorphic graphs] Two graphs $G_1, G_2$ are isomorphic (symbol $\cong$) if there is a bijection $\phi: V(G_1) \rightarrow V(G_2): xy \in E(G_1) \Leftrightarrow \phi(x)\phi(y) \in E(G_2)$. \end{definition} \begin{definition}[Complement] The complement of $G=(V,E)$ is $\bar{G} = (V, V^{(2)} \setminus E)$. \end{definition} \begin{example}[$C^5$ isomorphic to $\bar{C^5}$] \end{example} % 20031003 (2) \begin{definition}[Subgraph] A subgraph of a graph $G$ is a graph $H$ with $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$. \end{definition} \begin{definition}[Induced subgraph] $H$ is an induced subgraph if $E(H) = E(G) \bigcap V^{(2)}(H)$. The induced subgraph with vertex set $W \subseteq V(G)$ is written $G[W]$. \end{definition} \begin{definition}[Spanning subgraph] $H$ is a spanning subgraph if $V(H) = V(G)$. \end{definition} \begin{definition}[Walk] A walk in a graph is a sequence of vertices $v_1,v_2,\cdots,v_k \in E(G) \forall 1 \le i < k$. Its length is $k-1$. It is closed if $v_1 = v_k$. \end{definition} \begin{definition}[Trail] A trail is a walk with no repeated edges. \end{definition} \begin{definition}[Euler trail/circuit] An Euler trail/circuit is a trail or circuit which passes through all the edges. \end{definition} \begin{definition}[Eulerian] A graph is Eulerian if it has an Euler circuit. \end{definition} \begin{definition}[Path] A path is a walk (a trail) with no repeated vertices. \end{definition} \begin{definition}[Cycle] A cycle is a closed walk of length $\ge 3$ with distinct vertices except that the frist and last are equal (isomorphic to $C_n$). \end{definition} \begin{definition}[Hamilton trail/circuit] A Hamilton path/cycle is a path/cycle which goes through every vertex of the graph. \end{definition} \begin{definition}[Hamiltonian] A graph is Hamiltonian if it has a Hamilton cycle. \end{definition} \begin{definition}[Neighbours of a vertex] Let $x$ be a vertex of $G$, its neighbours or adjacent vertices are $\Gamma(x) = \{ y \in V(G): xy \in E(G) \}$. \end{definition} \begin{definition}[Degree of a vertex] The degree of a vertex $x$ is $d(x) = \norm{\Gamma(x)}$. \end{definition} \begin{definition}[Degree sequence of a graph] The degree sequence of a graph is a graph with vertices $v_1,\cdots,v_n$ is $d(v_1),\cdots,d(v_n)$. \end{definition} \begin{definition}[Maximum, minimum degree] The minimum/maximum degree of a vertex of $G$ is denoted $\delta(G)$ or $\Delta(G)$ respectively. \end{definition} \begin{definition}[Regular] A graph $G$ is regular if $\delta(G) = \Delta(G)$. \end{definition} \begin{definition}[Size of a graph] $e(G) = \norm{E(G)}$ is the number of edges of $G$, its size. \end{definition} \begin{definition}[Order of a graph] $\norm{G} = \norm{V(G)}$ is the number of edges of $G$, its order. \end{definition} % 20031013 (3) \begin{lemma}[Handshaking lemma] $\sum_{v \in V(G)} d(v) = 2e(G)$ \end{lemma} \begin{proof} Double count $\{ (x,xy) : x \in V(G), xy \in E(g) \}$. \end{proof} \begin{observation} To solve problems try induction (on vertices, edges, and other things), try double counting (counting something in more than one way), consider the pigeon hole principle and consider extreme cases. \end{observation} % 20031015 (1) \begin{definition}[Connected] A graph is connected if every pair of vertices is joined by a path. The relationship on $V(G)$ where $x \sim y$ where is a path between $x$ and $y$ is an equivalence relation. The equivalence classes are called components of $G$. \end{definition} \begin{definition}[Acyclic] A graph is acyclic if it has no cycles. \end{definition} \begin{definition}[Tree] A tree is a connected acyclic graph. \end{definition} \begin{definition}[Forest] A forest is an acycle graph. \end{definition} % 20031015 (2) \begin{theorem}[Properties of a tree] The following are equivalent \begin{enumerate} \item $G$ is a tree (connected, acyclic) \item $G$ is minimal connected \item $G$ is maximal acyclic \end{enumerate} \end{theorem} \begin{proof} % XXX case i $\implies$ ii. Let $G$ be connected and acyclic. Let $uv \in E(G)$. If $G - uv$ were connected then any $u-v$ path in $G - uv$ would give a cycle in $G$. % XXX case ii $\implies$ i. If $C$ were a cycle in $G$ and $uv \in E(G)$ then any $x-y$ path in $G$ passing via $uv$ could be patched up to $C-uv$ to give a path in $G-uv$. Contradiction. i $\implies$ iii. Let $uv \notin E(G)$. Since $G$ connected $\exists u-v$ path in $G$ so there is a cycle in $G+uv$. Contradiction. iii $\implies$ i. Suppose $G$ is not connected. Let $u,v$ be vertices of $G$ belonging to different components. $G+uv$ contains no cycles. Contradiction. \end{proof} % 20031015 (3) \begin{corollary} A graph is connected iff it has a spanning tree (i.e. $G$ has a subgroup $T$, $T$ a tree and $V(T)=V(G)$). \end{corollary} \begin{proof} % case XXX <= Assume $G$ has a spanning tree $T$. Then there is a path in $T$ and so in $G$ between all vertices. % case XXX => Let $T$ be minimal connected spanning subgraph of $G$. By previous theorem it is a tree. \end{proof} \begin{definition}[Leaf] A leaf is a vertex $v$ with $d(v)=1$. \end{definition} \begin{lemma}[Trees have leaves] Every tree $T$ of order $n \ge 2$ has at least two leaves. \end{lemma} \begin{proof} Let $P = x_1 \cdots x_k$ be a path of maximal length in $T$. Then $\Gamma(x_1) \subset P$, since $P$ is maximal. $T$ is acyclic so $\Gamma(x_1) \cap P = \{ x_2 \}$. Similarly for $x_k$. \end{proof} % 20031015 (4) \begin{theorem}[Size of a tree] A tree of order $n$ has size $n-1$. $e(T) = \norm{T} - 1$. (In fact a connected graph $G$ with $e(T) = \norm{T} - 1$ is a tree, exercise.) \end{theorem} \begin{proof} By induction on $n$. Clearly true for $n \le 2$. Let $T$ be a tree of order $n$ and let $v \in V(T)$ be a leaf. Let $x,y$ be vertices of $T-v$. There is an $x-y$ path in $T$. So $T$ connected implies $T-v$ connected so $T-v$ is a tree. By induction $e(T-v) = n-2 \implies e(T) = e(T-v)+1 = n-1$. \end{proof} \begin{observation}[Number of possible graphs] If vertices are labelled $1,\cdots,n$ there are $n \choose 2$ possible edges and each subset gives a graph so there are $2^{n \choose 2}$ possible graphs. If the vertices are unlabelled then each graph can be labelled in at most $n!$ possible ways. So there are at least $\frac{2^{n \choose 2}}{n!}$ graphs. \end{observation} % 20031015 (5) \begin{theorem}[Cayley] There are $n^{n-2}$ labelled trees of order $n$. \end{theorem} \begin{proof} (Due to Pr{\"u}fer.) Given a labelled tree we constract a sequence of $n-2$ numbers in the range $1,\cdots,n$ as follows. Select the lowest labelled leaf. Write down its neighbour. Delete the leaf. Repeat until just two vertices remain. Now have a function $f$ from set of labelled trees of order $n$ to $\{ 1, \cdots n \}^{n-2}$. % XXX case injectivity Claim: $f$ is injective. Each vertex $v$ appears $d(v)-1$ times in the sequence. Leaves are vertices not appearing. Given a sequence $(a_1,\cdots,a_{n-2})$ let $v_1$ be the least vertex not appearing, join it to $a_1$. Let $v_2$ be the least vertex not appearing in the new sequence $(v_1,a_2,\cdots,a_{n-2})$, join it to $a_2$. Repeat until there are only two nodes not in $(v_1,\cdots,v_{n-2})$, join them together. The original graph is reconstructed. % 20031015 (6) Claim: $f$ is surjective. Every sequence produces a connected acyclic graph $G$ with $e(G) = \norm{G} - 1$ which must be a tree (or else add more edges to make a tree and produce a contradiction). Deduce that $f$ is a bijection. \end{proof} % 20031020 (1) \begin{definition}[Bipartite] A graph is bipartite with vertex classes $X,Y$ if $X$ and $Y$ partition $V(G)$ and no edge of $G$ lies within $X$ or $Y$ (every edge goes between them). We say that $X$ and $Y$ are independent sets. We sometimes think of colouring $X$ red and $Y$ blue. \end{definition} \begin{theorem}[K{\"o}nig] A graph is bipartite iff it contains no odd cycles. \end{theorem} \begin{proof} % XXX case => Any cycle alternates between the two vertex classes, so has even length. % XXX case <= We may suppose that the graph $G$ is connected, since a graph is bipartite if its components are bipartite. Let the distance $d(u,v)$ between $u,v \in V(G)$ be the length of the shortest $u-v$ path. Let $u \in V(G)$. Define $U_i = \{ v \in V(G) : d(u,v) = i \}$ for $i = 0,1,2,\cdots$. Note that an edge of $G$ can join vertices in $U_i$ and $U_j$ only if $j = i$ or $j = i + 1$ or $j = i - 1$. % 20031020 (2) Claim. There is no edge between vertices in $U_i$. Proof. If $yy' \in E(G): y,y' \in U_i$ then select paths $u-y$ and $u-y'$ of length $i$. Let $w$ be the last common vertex. Then $w-y$,$w-y'$ and $yy'$ form a cycle of length $2(i - d(u,w)) + 1$ contradicting absence of odd cycles. Colour $U_0 \union U_2 \union U_4 \union \cdots$ red and $U_1 \union U_3 \union U_5 \union \cdots$ blue to give a bipartition of $G$. \end{proof} \begin{definition}[Complete bipartite graph $K_{m,n}$] $K_{m,n}$ is the complete bipartite graph with vertex classes of order $m$ and $n$ with all $mn$ edges. \end{definition} \begin{definition}[Planar graphs] A graph that can be drawn in the plane without crossings is planar. A graph drawn in the plane is a plane graph. \end{definition} \begin{definition}[Face or country] If we omit (``cut out'') the vertices and edges of a plane graph from the plane the remainder falls into connected components called faces or countries. \end{definition} % 20031020 (3) \begin{theorem}[Euler] Let $G$ be a connected plane graph with $n$ vertices, $e$ edges and $f$ faces. Then $n - e + f = 2$. \end{theorem} \begin{proof} By induction on $e = e(G)$. If $e = n-1$ then $G$ is a tree and $f = 1$. Done. If $e > n-1$ there is a cycle $C$ in $G$. Then any $xy \in E(C)$ separates two different faces. Apply induction to $G - xy$ gives $n - (e-1) + (f-1) = 2$. \end{proof} \begin{observation} It is convenient to use stereographic projection to consider a plane graph as drawn on the sphere. Then $G$ is connected iff all the faces are simply connected (homeomorphic to the unit disc). \end{observation} % 20031020 (4) \begin{definition}[Bridge] A bridge in a plane graph is an edge whose removal increases the number of components. \end{definition} \begin{definition}[Bridgeless] In a bridgeless plane graph every edge separates two different faces. $2e(G) = \sum_i {i f_i}$ where $f_i$ is the number of $i$-sided faces. \end{definition} \begin{definition}[Girth] The girth of a graph $G$ is the length of the shortest cycle. \end{definition} \begin{theorem}[Bound for number of edges in a planar graph] Let $G$ be a bridgeless plane graph with $n$ vertices and girth $g$. Then $e(G) \le \frac{g}{g - 2} (n-2)$. In particular a plane graph has at most $3n - 6$ edges. \end{theorem} \begin{proof} Add edges if necessary to ensure that $G$ is connected. It remains bridgeless and planar. Then $2e = \sum_i i f_i \ge g \sum_i f_i = gf$. So $f \le \frac{2e}{g}$. By Euler's theorem $n-2=e-f$. But $e -f \ge e - \frac{2e}{g} = \frac{g -2}{g} e \implies e \le \frac{g}{g - 2} (n-2)$. \end{proof} % 20031020 (5) \begin{theorem}[Kuratowski (unproved)] Kuratowski showed that the only non-planar graphs are those that contain a subdivision of $K_5$ or $K_{3,3}$ obtained by replacing edges with paths. \end{theorem} \begin{theorem}[Eulerian condition] A graph is Eulerian iff it is connected and every vertex has even degree. \end{theorem} \begin{proof} % XXX case => If the graph is Eulerian it must be connected. If a vertex has odd degree the path must pass in a different number of times from that which it passes out. % XXX case <= By induction on the number of edges. True for the empty graph. Since $\delta(G) \ge 2$ there are no leaves so $G$ is not a tree. Therefore $G$ must contain a cycle $C$. Each component of $G \setminus E(C)$ has vertices of even degree, so by induction hypothesis each has an Euler circuit. By traversing $C$ take time out to traverse each of these circuits when first encountered. We produce an Euler circuit for $G$ as $G$ is connected. \end{proof} % 20031022 (2) -- yes it does belong before (1) \begin{corollary} A connected graph $G$ has an Euler trail from a vertex $x$ to a vertex $y \ne x$ iff $x$ and $y$ are the only vertices of odd degree. \end{corollary} \begin{proof} % XXX case => If there is an Euler trail then obvious. % XXX case <= If $x$ and $y$ are the only vertices of odd degree then form $G'$ by adding a new vertex $u$ and joining it to $x$ and $y$. By the theorem $G'$ has an Euler circuit. Deleting $u$ gives an Euler trail from $x$ to $y$. \end{proof} % 20031022 (1) \chapter{Flows, connectivity and matching} \begin{definition}[Flow] A flow in a digraph $D$ with source $s$ and sink $t$ is a function $f: E(D) \mapsto \R_{\ge 0}$ such that $f_+(x) = f_-(x)$ $\forall x \in V(D) \setminus \{ s,t \}$ where $f_+(x) = \sum_{y: xy \in E(D)} f(xy)$ (the flow out of $x$) and $f_-(x) = \sum_{y: yx \in E(D)} f(yx)$ (the flow into $x$). Convenient to set $f(xy)=0$ if $xy \notin E(G)$. \end{definition} \begin{definition}[Directed edge] $xy$ is the directed edge from $x$ to $y$. Loops and multiple edges are forbidden, so certainly $f(xy) = 0$ or $f(yx) = 0$. \end{definition} \begin{observation} We imagine $f$ as representing a flow of water or electricity in a network, being pumped in at $s$, and being pumped out at $t$. The condition $f_+(x) = f_-(x)$ expresses that flow is conserved at each vertex. \end{observation} \begin{definition}[Value of the flow] $v(f)=f_+(s)-f_-(s)=f_-(t)-f_+(t)$ is called the value of the flow where $s$ is the source and $t$ is the sink. \end{definition} % 20031022 (3) \begin{definition}[Net flow] Let $S \subseteq V(D)$ with $s \in S$ and $t \notin S$. Let $\bar{S} = V(D) \setminus S$. The net flow from $S$ to $\bar{S}$ is $f(S,\bar{S}) = \sum_{x \in S,y \in \bar{S}}(f(xy) - f(yx))$. Since $\sum_{x,y \in S}(f(xy) - f(yx)) = 0$ we get $f(S,\bar{S}) = \sum_{x \in S,y \in V}(f(xy) - f(yx)) = \sum_{x \in S}(f_+(x) - f_-(x)) = f_+(s) - f_-(s) = v(f)$. \end{definition} \begin{definition}[Capacity function] Given a capacity function $c: E(D) \mapsto \R_{\ge 0}$ we require that $0 \le f(xy) \le c(xy)$ for all $xy \in E(D)$. \end{definition} \begin{definition}[Cut] Let $S \subseteq V(D)$ with $s \in S$ and $t \notin S$. Let $\bar{S} = V(D) \setminus S$. The set of edges $E(S,\bar{S}) = \{ xy \in E(D) : x \in S, y \in \bar{S} \}$ is called a cut with capacity $c(S,\bar{S}) = \sum_{x\in S,y \in \bar{S}} c(xy)$. % 20031022 (4) For any cut we have $v(f) = f(S,\bar{S}) \le c(S,\bar{S})$. \end{definition} \begin{theorem}[Max-flow min-cut (MFMC)] The maximum value of a flow (source $s$ and sink $t$) in a network is equal to the minimum cut capacity. \end{theorem} \begin{proof} The maximum flow in a network is less than or equal to the minimum cut capacity. Let $f$ be a flow. We construct $S \subseteq V(D)$. Initially let $S = \{ s \}$. Then put $y \in S$ if either $\exists x \in S: f(xy) < c(xy)$ or $\exists x \in S$ with $f(yx) > 0$. Repeat. % XXX case If $t \in S$ then there is a sequence of vertices starting with $s = y_0, y_1,\cdots, y_k = t$ where for each $1 \le i \le k$ either $c(y_{i-1},y_i) - f(y_{i-1},y_i) = \delta_i > 0$ or $f(y_i,y_{i-1}) = \delta_i > 0$. Let $\delta = min_{1 \le i \le k} \delta_i$. We construct a new flow $f: E(D) \mapsto \R_{\ge 0}$ equal to $f$ except on the $s-t$ path but with $f'(y_{i-1},y_i) = f(y_{i-1},y_i) + \delta$ or $f'(y_i,y_{i-1}) = f(y_i,y_{i-1}) - \delta$ as appropriate. $f'$ is a flow. $v(f') = v(f) + \delta$ so $f$ was not maximal, contradiction. Algorithm increases. Take a subsequence monotonic on each edge. Take the limit. This flow has value of limit so it is maximal. % XXX case If $t \notin S$. Let $\bar{S} = V(D) \setminus S$. $E(S,\bar{S})$ is a cut. For every $xy$ with $x \in S$ and $y \in \bar{S}$ we have $f(xy) = c(xy)$. For every edge $yx$, $x \in S$ $y \in \bar{S}$ we have $f(yx) = 0$. $v(f) = f(S,\bar{S}) = \sum_{x \in S, y \in \bar{S}}(f(xy)-f(yx)) = \sum_{x \in S, y \in \bar{S}} c(xy)$. That is, the value of the flow is the cut capacity of some cut. \end{proof} % 20031022 (5) \begin{corollary}[Integrability theorem] In a network with integer valued edge capacities there is a maximal flow whose value is equal to the minimum cut capacity, which has integer values at each edge. \end{corollary} \begin{proof} Follow MFMC starting with the zero flow. Then $\delta$ is always integer. \end{proof} \begin{observation} Note that there may be a maximal flow which is not integer valued on each edge. \end{observation} \begin{definition}[Multiple sinks and sources] Consider multiple sources $s_1,\cdots,s_k$ and multiple sinks $t_1,\cdots,t_k$. The value of the flow is $v(f) = \sum_{i=1}^{k}(f_+(s_i)-f_-(s_i)) = \sum_{j=1}^{l}(f_-(t_j)-f_+(t_j))$ and a cut is $E(S,\bar{S})$ where $s_1,\cdots,s_k \in S$ and $t_1,\cdots,t_k \in \bar{S}$. \end{definition} \begin{corollary}[MFMC for multiple sources and sinks] In a multiple source network the maximum value of a flow is equal to the minimum cut capacity. \end{corollary} \begin{proof} We construct a new network by joining a supersource $s$ to $s_1,\cdots,s_k$ and a supersink $t$ to $t_1,\cdots,t_l$ using edges of infinite capacity. % 20031027 (2) Apply MFMC. Note that any cut of finite capacity cannot touch edges $s s_i$ or $t_j t$ so cut can be applied to original graph. \end{proof} \begin{definition}[Vertex capacities] We can consider vertex capacities instead of edge capacities. The capacity function is now $C : V(D) \setminus \{ s,t \} \mapsto \R_{\ge 0}$ and we want $0 \le f_+(v)=f_-(v) \le c(v)$ $\forall v \in V(D) \setminus \{ s,t \}$. A cut is now a set of vertices $S$ such that $D-S$ has no $s-t$ path. It has capacity $\sum_{v \in S} c(v)$. \end{definition} \begin{corollary}[Vertex capacity version of MFMC] The maximum value of a flow in a network with vertex capacities is equal to the minimum cut capacity. \end{corollary} \begin{proof} Construct from $D$ a new network $D'$ with edge capacities. Replace each vertex $v$ by two vertices $v_-$ and $v_+$ and an edge $v_-v_+$. For each edge $xy \in E(D)$ add an edge $x_+y_-$ to $D'$. We give $v_-v_+$ capacity $c(v)$ give $x_+y_-$ infinite capacity. Apply MFMC. \end{proof} % 20031027 (3) \chapter{Connectivity and the theorems of Menger} \begin{definition}[Notation for subgraphs] If $G$ graph and $S \subseteq V(G)$ then $G-S$ is the induced subgraph with edges in $S$ deleted. Given $F \subseteq E(G)$ then $G-F$ is the spanning subgraph obtained by deleting edges in $F$. \end{definition} \begin{definition}[$k$ connected] A graph is $k$ connected if $|G| > k$ and $G-S$ is connected for any $S \subset V(G)$ with $|S| < k$. \end{definition} \begin{observation} The only $k$ connected graph with $k+1$ vertices is the complete graph $K_{k+1}$. \end{observation} \begin{definition}[Connectivity] The connectivity of $G$ or $\kappa(G) = \max \{ k : G $is$ k-$connected$\}$. \end{definition} \begin{definition}[Local connectivity] If $a,b \in V(G)$ distinct and $ab \notin E(G)$ the local connectivity $\kappa(a,b;G) = \min \{ k : \exists S \subseteq V(G) \setminus \{ a,b \} : |S| = k : G - S$ has no $a-b$ path $\}$, the minimum number vertices separating $a$ and $b$. \end{definition} \begin{observation} If $G$ is not complete then $\kappa(G) = \min_{a,b} \{ \kappa(a, b; G) \}$, which is the same as $\min_{a,b : ab,ba \notin E(G)} \{ \kappa(a, b; G) \}$. If $G$ is complete then $\min_{a,b} \{ \kappa(a, b; G) \}$ does not have a value, but $\kappa(K_n) = n-1$. \end{observation} \begin{definition}[$k$-edge connected] A graph $G$ is $k$-edge connected if $G-F$ is connected for all $F \subseteq E(G)$ with $|F| < k$. \end{definition} \begin{definition}[Edge connectivity $\lambda(G)$] The edge connectivity of $G$ is $\lambda(G) = \max \{ k : G$ is $k$ edge connected$ \}$. \end{definition} \begin{definition} If $a,b \in V(G)$ distinct then the local edge connectivity is $\lambda(a,b; G) = \min \{ k: \exists F \subseteq E(G) : |F| = k, G - F$ has no $a-b$ path $ \}$. Note that $\lambda(G) = \min_{a,b} \lambda(a,b;G)$. \end{definition} % 20031027 (4) \begin{definition}[Independent paths] Two $a-b$ paths are independent if their only common vertices are $a,b$. \end{definition} \begin{theorem}[Menger] Vertex form. Let $a,b \in V(G)$ distinct. $ab \notin E(G)$ then $\kappa(a,b;G) = $ maximum number of pairwise independent $a-b$ paths. Edge form. $a,b \in V(G)$ distinct. Then $\lambda(a,b;G) = $ maximum number of edge disjoint $a-b$ paths. \end{theorem} \begin{proof} Vertex form. Replace all edges $uv \in E(G)$ with two directed edges and give each vertex capacity 1. Apply vertex form of max-flow min-cut to get an integer flow from $a-b$, $\kappa(a,b;G)$ since each vertex has capacity $1$ or $0$. Edge form. Do the same thing but use the edge form of max-flow min-cut. \end{proof} \begin{definition}[Line graph] The line graph $L(G)$ is the graph with a vertex $v_e$ for each $e \in E(G)$ and an edge $v_e v_f$ whenever $e$ and $f$ have a common end vertex in $G$. \end{definition} \begin{observation} The edge form can be deduced from the vertex from, using the line graph. \end{observation} \begin{observation} Given a set $P$ of independent $a-b$ paths then certainly $|P| \le \kappa (a,b;G)$, but it is not necessarily possible to add paths to $P$ to form $\kappa (a,b;G)$ independent paths. \end{observation} \begin{observation} There is a multiple source - sink version of Menger's theorem. \end{observation} \begin{lemma} Assume $ab \in E(G)$ and let $G' = G - ab$. Then $\kappa(a,b;G') \ge \kappa(G) - 1$. \end{lemma} \begin{proof} Let $k = \kappa(a,b;G')$. Choose $S \subseteq V(G) \setminus \{ a,b \}$ with $|S|=k$ and $G' - S$ disconnected. Let $x$ and $y$ be vertices in different components of $G'-S$, so that $|\{x,y\} \intersect \{ a,b \}|$ is minimal. Then either \begin{enumerate} \item $a \ne x,y$ so $G - (S \union {a})$ is disconnected; or \item $b \ne x,y$ so $G - (S \union {b})$ is disconnected; or \item $\{ x,y \} = \{ a,b \}$ so $V(G) = S \union \{ a,b \}$, so $|G| \le k+2$. \end{enumerate} All cases imply that $\kappa(G) \le k+1$. \end{proof} \begin{corollary} A graph is $k$-connected iff any two vertices are joined by at least $k$ independent paths. \end{corollary} \begin{proof} If $G$ is not a complete graph, $\kappa(G) = \min \kappa(a,b;G)$. Apply Menger's theorem. $K_n$ is $k$-connected iff $n \ge k+1$, so true for a complete graph. \end{proof} \begin{corollary} A graph is $k$-edge-connected iff any two vertices are joined by at least $k$ edge disjoint paths. \end{corollary} \chapter{Matchings} \begin{definition}[$k$-factor] A $k$-factor of a graph $G$ is a $k$-regular spanning subgraph, that is, a subgraph $H$ with $\delta(H) = \Delta(H) = k$. \end{definition} \begin{definition}[Matching] Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. A matching in $G$ is a set of $|X|$ independent edges. If $|X| = |Y|$ then a matching is a 1-factor. \end{definition} \begin{theorem}[Hall's marriage theorem] Let $G$ be a bipartite graph with vertex classes $X$ and $Y$. Then $G$ has a matching iff $|\Gamma(S)| \ge |S|$ for every $S \subseteq X$. \end{theorem} \begin{proof}[Using Menger's theorem] Join a new vertex $a$ to all elements of $X$ and a new vertex $b$ to all elements of $Y$ to form $G'$. Suppose $C$ is a set of vertices separating $a$ from $b$. Then $\Gamma(X \setminus C) \subseteq Y \intersect C$. Now $|C| = |C \intersect X| + |C \intersect Y|$. So $|C| \ge |C \intersect X| + |\Gamma(X \setminus C)|$. By Hall's condition $|\Gamma(X \setminus C)| \ge |X\setminus C|$. So $|C| \ge |C \intersect X| + |X \setminus C| = |X|$. By the choice of $C$, $\kappa(a,b;G) \ge |X|$. Using Menger's theorem there are $|X|$ independent paths, giving a matching in $G$. \end{proof} \begin{proof}[Direct] By induction on $|X|$. The case $|X| \le 1$ is trivial. Suppose that for every $S \subset X$ with $S \ne \emptyset,X$ we have $|\Gamma(S)| > |S|$. Then take any $xy \in E(G)$. $G - x$ satisfies Hall's condition. By the induction hypothesis $G - \{ x,y \}$ has a matching, so $G$ has a matching. Otherwise there exists a critical set $T \subset X$, $T \ne \emptyset, X$ with $|\Gamma(T)| = |T|$. Let $G_1 = G[T\union \Gamma(T)]$ and $G_2 = G[(X \setminus T) \union (Y \setminus \Gamma(T))]$. $G_1$ clearly satisfies Hall's condition. Let $S \subseteq X\setminus T$. Now $\Gamma_{G_2} (S) = \Gamma_G (S \union T) \setminus \Gamma_G (T)$. \[ |\Gamma_{G_2} (S)| \ge |\Gamma_G (S \union T)| - |\Gamma_G (T)| \] \[ \ge |S \union T| - |T| = |S| \] So by induction hypothesis there is a matching on $G_1$ and $G_2$, giving a matching in $G$. \end{proof} \begin{corollary}[Defect form of Hall's theorem] Let $d \ge 0$ be an integer. If $|\Gamma(S)| \ge |S| - d$ for all $S \subseteq X$ then there is a matching of all but $d$ elements of $X$. \end{corollary} \begin{proof} Add $d$ extra vertices to $Y$ connected to all vertices of $X$. Then by Hall's theorem there is a matching. Remove the additional vertices, to make a matching of all but $d$ elements of $X$. \end{proof} \begin{corollary}[Polygamous form] Let $d \ge 1$ be an integer. If $|\Gamma(S)| \ge d|S|$ for all $S \subseteq X$, then we can match each $x \in X$ to $d$ elemens of $Y$, the different $d$ element sets being disjoint. \end{corollary} \begin{proof} Replace each $x \in X$ with $d$ nodes connected to $\Gamma(x)$. Hall's theorem gives a matching. \end{proof} \chapter{Extremal graph theory} \begin{definition}[Monotone] A property of a graph is monotone if the whole graph has the property when a subgraph does. \end{definition} \begin{definition}[Non-trival property] A property of a graph is non-trivial if the empty graph does not have the property. \end{definition} \begin{definition}[Extremal problem] The study of the minimum size of a graph with a monotone, non-trivial property, or the maximum size of a graph without it. \end{definition} \begin{theorem}[Condition for a graph to be Hamiltonian]\label{hamiltonianness} Let $G$ be a connected graph of order $n \ge 3$. Suppose that for every pair of non-adjacent vertices $a,b$, $d(a)+d(b) \ge k$. If $k < n$ then $G$ has a path of length $k$. If $k \ge n$ then $G$ is Hamiltonian. Note that if $k \ge n$ then the degree condition implies that $G$ is connected. \end{theorem} \begin{proof} Suppose that $G$ is not Hamiltonian. Let $P = x_1 \cdots x_l$ be a path of maximal length. Claim. $G$ has no cycle of length $l$. Proof of claim. Suppose there is a cycle. Obviously if $l = n$ then $G$ is Hamiltonian, contradiction. If $l < n$ then there is a vertex $w$ not in the cycle. $G$ is connected, so we can find a path from the cycle to $w$, giving a path longer than $l$, contradiction. In particular, $x_1 x_l \notin E(G)$. Now by hypothesis $d(x_1) + d(x_l) \ge k$. Let $S = \{ 2 \le i \le l : x_1 x_i \in E(G) \}$, $T = \{ 2 \le i \le l : x_{i-1} x_l \in E(G) \}$. If $j \in S \intersect T$ then $x_1 x_j x_{j+1} \cdots x_l x_{j-1} x_{j-2} \cdots x_1$ is a cycle of length $l$. So $S \intersect T = \emptyset$. Certainly $l \notin S,T$ and $S \union T \subseteq \{ 1,\cdots, l \}$, so in fact $k \le d(x_1) + d(x_l) = |S| + |T| \le l - 1$. If $k < n$ then we have a path of length $l-1 \ge k$, so a path of length $k$. If $k = n$ then we have a path of length $n$, which is a contradiction because it must involve $n+1$ vertices. Therefore $G$ is Hamiltonian. \end{proof} %\begin{observation} % The inequality is exact. % Let $k$ be even. Consider $G$ composed of copies of % $K_{\frac{k}{2}}$ and an additional vertex joined to all others. % Then $\delta(G) = \frac{k}{2}$ but $G$ contains no path of length % $k+1$. Furthermore $G$ has no cycle of length $> \frac{k}{2} + 1$. % By the theorem there is a cycle of length $\ge \frac{k}{2} + 1 \begin{corollary}[G.A. Dirac] If $\delta(G) \ge \frac{n}{2}$ then $G$ is Hamiltonian. \end{corollary} \begin{theorem} Let $G$ be a graph with $n$ vertices and no path of length $k$. Then $e(G) \le (k - 1) \frac{n}{2}$ with equality iff $G$ is a union of copies of $K_k$. \end{theorem} \begin{proof} By induction on $n$. If $n \le k$ then $e(G) \le {n \choose 2} \le (k - 1) \frac{n}{2}$ with equality iff $G = K_k$. Consider $n > k$. If $G$ is disconnected apply induction to each component. Otherwise $G$ is connected and $K_k \not \subset G$, or there would be a vertex $w$ that could be joined to a path traversing the $K_k$ to make a path of length $k$. By theorem \ref{hamiltonianness} at least one $v \in V(G)$ has $d(v) \le \frac{k-1}{2}$. By the induction hypothesis $e(G-v) < \frac{k-1}{2}(n-1)$. Therefore $e(G) < \frac{k-1}{2}n$. \end{proof} \section{Complete subgraphs and Tur{\'a}n's theorem} We've seen the maximum size of a graph containing no path of a certain length. What is the maximum size of a graph containing no $K_r$? \begin{definition}[$r$-partite graph] An $r$-partite graph is a graph with a vertex partition $V_1,\ldots,V_r$ so that each $V_i$ is an independent set (i.e. $G[V_i]$ is empty of edges). \end{definition} Certainly no $(r-1)$-partite graph contains $K_r$. What is the maximum size of a $(r-1)$-partite graph? Clearly we should look at a complete $(r-1)$-partite graph, where any pair of vertices in different classes are joined. Suppose two class orders differ by more than 1, $|V_i| \ge |V_j| + 2$. Moving a vertex from $V_i$ to $V_j$ increases the number of edges by $|V_i| - |V_j| - 1 \ge 1$. Therefore the classes are as equal as possible. \begin{definition}[Tur{\'a}n graph, $T_r$ and $t_r$] The Tur{\'a}n graph $T_r(n)$ is the complete $r$-partite graph of order $n$ with classes orders $\floor{\frac{n}{r}}$ or $\ceil{\frac{n}{r}}$. We write $t_r(n) = e(T_r(n))$. \end{definition} \begin{theorem}[Tur{\'a}n's theorem; maximum sized graph not containing $K_r$] Let $G$ be a $K_r$ free graph of order $n$ with $e(G) \ge t_{r-1}(n)$ then $G$ = $T_{r-1}(n)$. \end{theorem} \begin{proof} The vertices in $T_r(n)$ with least degree belong to vertex class of greatest order, by removing one of these we get $T_r(n-1)$. \begin{equation} t_{r-1}(n) - \delta(T_{r-1}(n)) = t_{r-1}(n-1) \label{turan_remove} \end{equation} Furthermore the degrees are as equal as possible. \begin{equation} \Delta(T_{r-1}(n)) - \delta(T_{r-1}(n)) \le 1 \label{turan_degrees} \end{equation} By induction on $n$. True for $n \le r - 1$, because $T_{r-1}(n)$ is $K_n$ for $n \le r -1$. In general let $G' \subset G$ be a spanning subgraph with $t_{r-1}$ edges. Certainly $G'$ is also $K_r$ free. Now apply the handshaking lemma to $G'$ \[ n\delta(G') \le 2e(G') \] \[ = 2 t_{r-1} \] \[ \le \delta(T_{r-1}(n)) + (n-1)\Delta(T_{r-1}(n)) \] Using \ref{turan_degrees} \[ \le n\delta(T_{r-1}(n)) + n - 1 \] \[ \delta(G') \le \delta(T_{r-1}(n)) \] Pick $v \in V(G')$ a vertex of minimum degree. Then $G' - v$ is again $K_r$-free. \[ e(G'-v) = e(G') - \delta(G') \] \[ = t_{r-1}(n-1) \] by \ref{turan_remove}. So by the induction hypothesis, $G' - v$ is a complete $(r-1)$-partite graph. In $G'$, $v$ cannot be joined to all vertex classes in $G' - v$, since otherwise $G'$ would contain $K_r$. So $G'$ is $(r-1)$-partite. But $e(G') = t_{r-1}(n)$ and $T_{r-1}(n)$ is the only $(r-1)$-partite graph of that size, so $G' = T_{r-1}(n)$. Adding any new edge to $T_{r-1}(n)$ creates a $K_r$, so $G = G' = T_{r-1}(n)$. \end{proof} \begin{theorem}[Tur{\'a}n's theorem; alternative forumulation and proof] Let $G$ be a $K_r$-free graph with vertex set $V$. Then there exists a $(r-1)$-partite graph $H$ with vertex set $V$, and $d_H(v) \ge d_G(v)$ for all $v \in V$. \end{theorem} \begin{proof} By induction on $r$. Case $r = 2$ trivial. In general, we pick $x$ a vertex of $G$ of maximum degree. Let $G' = G[\Gamma(x)]$. Then $G'$ is $K_{r-1}$ free. Let $V' = \Gamma(x)$. By induction, there is a $(r-2)$-partite graph $H'$ with vertex set $V'$ and $d_{H'}(v) \ge d_{G'}(v)$ $\forall v \in V'$. Form $H$ by joining every vertex in $V \setminus V'$ to $H'$. Now construct $H$ by joining every vertex in $V \setminus V'$ to $H'$. Then $H$ is $(r-1)$-partite. Need to show $d_H(v) \ge d_G(v)$ for all $v \in V$. If $v \in V \setminus V'$, $d_H(v) = \norm{V'} = d_G(x)$. But $d_G(x) \ge d_G(v)$ $\forall v \in V$. Otherwise, $v \in V'$. $d_H(v) = \norm{V \setminus V'} + d_{H'}(v)$. But $d_{H'}(v) \ge d_{G'}(v)$. Now $d_{G}(v) \le d_{G'}(v) + \norm{V \setminus V'}$, so $d_H(v) \ge d_G(v)$. Done. \end{proof} \begin{lemma}[Alternative formulation of Tur{\'a}n's theorem implies original] Let $G$ be a $K_r$ free graph of order $n$ with $e(G) \ge t_{r-1}(n)$ then $G$ = $T_{r-1}(n)$. \end{lemma} \begin{proof} Only remains to show $e(G) \le t_{r-1}(n)$, as certainly $T_{r-1}(n)$ is the unique $(r-1)$-partite graph of size $t_{r-1}(n)$. By previous theorem there exists a $(r-1)$-partite graph $H$ with vertex set $V(G)$, and $d_H(v) \ge d_G(v)$ for all $v \in V(G)$. $e(G) = \frac{1}{2} \sum_{v\in V}(d_G(v) \le \frac{1}{2} \sum_{v \in V} d_H(v) = e(H)$. Now certainly $H$ is $(r-1)$-partite, and $t_{r-1}(n)$ is the maximum number of edges of an $(r-1)$-partite graph. So $e(G) = e(H) \le t_{r-1}(n)$. \end{proof} \begin{lemma}[Variant on the alternative formulation of Tur{\'a}n's theorem] Let $G$ be a graph of order $n$, and let $x \in V(G)$ of degree $d = \Delta(G)$. If $e(G[\Gamma(x)]) \le t_{r-2}(d)$, then $e(G) \le t_{r-1}(n)$. \end{lemma} \begin{proof} Let $V' = \Gamma(x)$. Let $H'$ be a copy of $T_{r-2}(d)$ with vertex set $V'$. Form an $(r-1)$-partite graph $H$ by joining every vertex in $V \setminus V'$ to $H'$. Certainly $e(H) \le t_{r-1}(n)$. Now $e(H) - e(H') \ge e(G) - e(G[V'])$, so if $e(G[V']) \le e(H')$ then $e(G) \le e(H) \le t_{r-1}(n)$. \end{proof} \begin{corollary}[Variant on alternative formulation of Tur{\'a}n's theorem] If $G$ has order $n$ and size $e(G) > t_{r-1}(n)$, then $G$ contains $K_r$ as a subgraph. \end{corollary} \begin{proof} By induction on $r$. Case $r = 2$ is trivial. In general we take a vertex $x \in V(G)$ with degree $d = \Delta(G)$. By the last lemma $e(G[\Gamma(x)]) > t_{r-2}(d)$ as $e(G) > t_{r-1}(n)$. By induction, $G[\Gamma(x)]$ contains $K_{r-1}$, so $G$ contains $K_r$. \end{proof} \begin{observation}[Method for finding $K_r$ in a graph] This corollary gives us an algorithm for finding $K_r$ in a graph that has more edges than $t_{r-1}(\norm{G})$. Take vertex $x_r$ of degree $\Delta(G)$. Let $G_r = G[\Gamma(x_r)]$. Given $x_n, G_n$ with $n > 1$, take $G_{n-1}$ to be $G_n[\Gamma_{G_n}(x_n)]$ and $x_{n-1}$ to be a vertex of highest degree in $G_n$. By the lemma, $G_n$, $n > 1$ contains $K_{n-1}$. Therefore $G[x_1,\cdots,x_r] \cong K_r$. \end{observation} \section{The problem of Zarankiewicz} \begin{definition}[Zarankiewicz problem, $z(n;t)$] The bipartite analogue of Tur{\'a}n's problem is to find the maximum number of edges $z(n;t)$ in an $(n,n)$-bipartite graph not containing a subgraph $K_{t,t}$. The value of $z(n;t)$ is not known. \end{definition} \begin{theorem}[Zarankiewicz] Let $y = \frac{1}{n} z(n;t)$. Then ${y \choose t} \le \frac{t-1}{n}{n \choose t}$. \end{theorem} \chapter{Graph colouring} \section{Vertex colouring and Brooks' theorem} \begin{definition}[Vertex colouring] A vertex $k$-colouring of a graph $G$ is a function $c: V(G) \mapsto \{ 1,2,\cdots,k \}$, such that $c(x) \ne c(y)$ $\forall xy \in E(G)$. We say $G$ is $k$-colourable if there is a $k$-colouring of $G$. Clearly $G$ is $k$-colourable iff it is $k$-partite. \end{definition} \begin{definition}[Chromatic number] The chromatic number $\chi(G)$ of a graph $G$ is the minimum $k$ for which $G$ is $k$-colourable. \end{definition} \begin{definition}[Greedy algorithm] Given an ordering $v_1,\cdots,v_n$ of $V(G)$, the greedy algorithm colours the vertices sequentially, giving vertex $v_i$ the smallest colour in $\{1,2,\cdots,n \}$ that is not in $c(\Gamma(v_i) \intersect \{ v_1,v_2,\cdots,v_{i-1} \})$. Clearly the number of colours used by the greedy algorithm depends on the order of the vertices. Furthermore given a colouring that uses only $\chi(G)$ colours it is possible to order the vertices so that the greedy algorithm will use no more than $\chi(G)$ colours. \end{definition} \begin{lemma}[Upper bound on $\chi(G)$] Given a graph $G$, $\chi(G) \le 1 + \Delta(G)$ \end{lemma} \begin{proof} Given a vertex $x$, then the greedy colouring algorithm will not give it a colour value more than $d(x) + 1$. Therefore the greedy colouring algorithm colours all graphs with no more than $\Delta(G) + 1$ colours, so $\chi(G) \le 1 + \Delta(G)$. \end{proof} \begin{theorem}[Upper bound on $\chi(G)$] \label{chi_upperbound} $\chi(G) \le 1 + \max_{H \subseteq G} \delta(H)$ where $H$ ranges over all induced subgraphs of $G$ (including $G$). \end{theorem} \begin{proof} We constructively describe a way of colouring $G$, by specifying a vertex order for the greedy colouring algorithm. Let $n = \norm{V}$. Let $H_n= G$. Let $x_n$ be a vertex in $H_n$ with degree $\delta(H_n)$. Certainly $\delta(G) < 1 + \max_{H \subseteq G} \delta(H)$. Let $H_{n-1} = H_n - \{ x_n \}$, $n > 1$. The sequence $x_1,x_2,x_3,\cdots,x_n$ presents to the greedy colouring algorithm a series of vertices which have had at most $\max_{H \subseteq G} \delta(H)$ neighbours already coloured. Therefore at most $1 + \max_{H \subseteq G} \delta(H)$ colours can be used. This bound is certainly exact for a complete graph. \end{proof} \begin{theorem}[Brooks] If $G$ is connected then $\chi(G) \le \Delta(G)$, unless $G$ is complete or $G$ is an odd cycle. \end{theorem} \begin{proof} Certainly by the greedy algorithm $\chi(G) \le \Delta(G) + 1$. Let $\Delta = \Delta(G)$. If $\chi(G) = \Delta + 1$ then by \ref{chi_upperbound} there is a subgraph $H$ of $G$ with $\delta(H) = \Delta$ ($H$ is $\Delta$-regular). But $G$ is connected and no vertex not in $H$ can connect to $H$, so $G = H$ and $G$ is $\Delta$-regular. Now suppose $Delta = 1$. Then $G = K_2$. Suppose $\Delta = 2$. Then $G = C_3$. Therefore we need only consider $\Delta \ge 3$. Sorry, but the rest of the proof will be omitted. The method is to take a vertex of degree $\Delta$ (the minimal degree) and as in the proof of Vizing's theorem, consider the components $H_ij$ of vertices coloured either $i$ or $j$ and the relationship its neighbours. By considering switching $i$,$j$ in these components one can show that the neighbours are pairwise joined. \end{proof} \begin{definition}[Chromatic polynomial] Let $G$ be a graph. Let $P_G(x)$ be the number of ways of colouring $G$ using $x$ colours. \end{definition} \begin{definition}[Notation for contracting edges $G/e$] Let $G$ be a graph. Let $e \in E(G)$. Then $G/e$ is the graph obtained by identifying the endpoints of $e$. That is if $e$ joins vertices $x,y$ then for each edge $yz$ join $z$ to $x$ if $z$ is not already joined to $x$. Then remove $y$. \end{definition} \begin{theorem}[Induction step on the chromatic polynomial] Let $e \in E(G)$. Then $P_G(x) = P_{G-e}(x) - P_{G/e}(x)$. \end{theorem} \begin{proof} Let $e = uv$. The colourings $c$ of $G-e$ that are not colourings of $G$ are those with $c(u) = c(v)$, which are precisely the colourings of $P_{G/e}(x)$. \end{proof} \begin{corollary}[The chromatic polynomial is a polynomial] $P_G(x)$ is a polynomial in $x$. Furthermore, $P_G(x) = x^n - a_1 x^{n-1} + a_2 x^{n-2} + \cdots + (-1)^n a_n$ with $n = \norm{G}$, $a_1 = e(G)$ and all $a_i \ge 0$. \end{corollary} \begin{proof} By induction on $e(G)$. True for the empty graph. In general let $e \in E(G)$. Now $P_{G-e}(x) = x^n - b_1 x^{n-1} + b_2 x^{n-2} + \cdots + (-1)^n b_n$, $P_{G/e}(x) = x^{n-1} - c_1 x^{n-2} + (-1)^(n-1) c_{n-1}$, where $n = \norm{G}$, $b_1 = e(G) -1$ and all $b_i,c_i \ge 0$. Now by the theorem, $P_G(x) = P_{G-e}(x) - P_{G/e}(x)$, so $P_G(x) = x_n - (b_1+1)x_{n-1} + (c_1 + b_2)x^{n-2} + \cdots + (-1)^n (b_n + c_{n-1})$, a polynomial of the same form. \end{proof} \chapter{Edge colouring and Vizing's theorem} \begin{definition}[Edge colouring] A $k$-edge colouring of a graph $G$ is a function $c: E(G) \mapsto \{ 1,2, \cdots, k \}$ such that incident edges receive different colours. \end{definition} \begin{definition}[Edge chromatic number, chromatic index] Given a graph $G$, the edge chromatic number or chromatic index $\chi'(G)$ is the least $k$ for which $G$ is $k$-edge-colourable. Certainly $\Delta(G) \le \chi'(G)$. \end{definition} \begin{theorem}[Vizing] $\Delta(G) \le \chi'(G) \le \Delta(G) + 1$ \end{theorem} \begin{proof} The lower bound is trivial. For the upper bound we do induction on the number of edges. Suppose we have a colouring of all but one edge $xy \in E(G)$ using colours $\{ 1,2,\cdots,\Delta(G) + 1 \}$. Then we wish to recolour so all the edges are coloured. Note that one colour is unused (``missing'') at every vertex. Let $x y_0$ be the uncoloured edge. We construct a sequence of edges $x y_0, x y_1, \cdots$ and a sequence of colours $c_0, c_1, \cdots$ as follows. Pick $c_i$ to be a colour missing at $y_i$. Let $x y_{i+1}$ be an edge with colour $c_i$. We stop with $k = i$ when either $c_k$ is a colour unused at $x$, or $c_k$ is already used on $x y_j$ for $j < k$. If $c_k$ was a colour unused at $x$ then we recolour $x y_i$ with $c_i$ for $0 \le i \le k$. This finishes the easy case where we can recolour the edges touching $x$ to give a a colouring for $G$. Otherwise we recolour $x y_i$ with $c_i$ for $0 \le i < j$ and uncolour $x y_j$. Notice that $c_k$ (red) is missing at both $y_j$ and $y_k$. Let blue be a colour unused at $x$. \begin{enumerate} \item If red is missing at $x$, we colour $x y_j$ red. \item If blue is missing at $y_j$ we colour $x y_j$ blue. \item If blue is missing at $y_k$ we colour $x y_i$ with $c_i$ for $j \le i < k$ and colour $x y_k$ blue. (None of the $x y_i$, $j \le i < k$ are red or blue.) \end{enumerate} If none of the above hold, then we consider the subgraph of red and blue edges. The components of this subgraph are paths or cycles. The vertices $x,y_i,y_k$ are the end vertices of paths. Therefore they cannot all belong to the same component. Select a component that contains exactly one of these vertices. Now swap over red and blue in this component. Now one of the conditions above must apply. \end{proof} \begin{theorem}[Edge chromatic number of a bipartite graph] If $G$ is bipartite, then $\chi'(G) = \Delta(G)$. \end{theorem} \begin{proof} We embed $G$ in a $\Delta(G)$-regular bipartite multi-graph as follows: We replace $G$ by two copies of $G$ and for $v',v''$, the copies of $v \in V(G)$, we join $v'$ to $v''$ with $\Delta(G) - d_G(v)$ parallel edges. This creates a bipartite multi-graph $H$ with vertex classes $(X' \union Y'')$ and $(Y' \union X'')$ if $X$ and $Y$ were the original vertex classes in $G$. Now we prove the theorem for $\Delta$-regular bipartite multi-graphs $H$ by induction on $\norm{H} + \Delta(H)$. Clearly true for $\Delta(H) = 1$. Let $uv$ be an edge of $H$, Delete the vertices $u$ and $v$. Because $u$ and $v$ were in different vertex classes, it is possible to add fewer than $\Delta$ new edges to make a new $\Delta$-regular bipartite multi-graph $H'$. Now we colour $H'$ by the induction hypothesis. Certainly not all the colours were used to colour the new edges. Let red be one of these colours. Certainly the red edges in $H'$ with $uv$ form a $1$-factor in $G$. Deleting this $1$-factor gives a $(\Delta-1)$-regular bipartite multigraph $H''$. Now colour $H''$ by the induction hypothesis, then add the $1$-factor back, to obtain a colouring of $H$. \end{proof} \begin{definition}[List colouring, $L$-choosable] Let $L : V(G) \mapsto \{ $ finite subsets of $\N$ $\}$, so that each vertex $v$ has a ``paint box'' $L(v)$. We say that $G$ is $L$-choosable if $\exists c: V(G) \mapsto \N$ such that $c(v) \in L(v)$ $\forall v$ and $c$ is a vertex colouring. \end{definition} \begin{definition}[$k$-choosable] We say that $G$ is $k$-choosable if $G$ is $L$-choosable whenever $\norm{L(v)} = k$, $\forall v \in V(G)$. Clearly if $G$ is $k$-choosable it is $k+1$-choosable. However it is not necessarily true that if $G$ is $k$-choosable it is $k$-colourable. \end{definition} \begin{definition}[List chromatic number $\chi_l(G)$] The list chromatic number $\chi_l(G)$ of a graph $G$ is the least $k$ such that $G$ is $k$-choosable. \end{definition} \chapter{Colouring graphs on surfaces} \section{Plane graphs} \begin{definition}[Dual graph $G*$] Given a plane graph $G$ we can form a new graph $G*$ by drawing a vertex in the middle of each of $G$'s faces, and joining vertices if their corresponding faces are adjacent. \end{definition} \begin{lemma}[Condition for duality of dual] $G** = G$ iff $G$ connected and $\lambda(G) > 2$. \end{lemma} \begin{proof} If $G*$ is always connected, so $G**$ is as well, so $G$ must be. Always $e(G*) \le e(G)$ as each edge in the original graph may be crossed at most once by an edge in the dual. If $\lambda(G)$ is $1$ then $G$ has a bridge, which certainly will not be crossed by an edge in the dual, so $e(G*) < e(G)$. If $\lambda(G)$ is $2$ then there is an edge, which if removed, would leave a bridge in $G$. so again $e(G*) < e(G)$. In both cases $e(G**) \le e(G*) < e(G)$. If $\lambda(G) \ge 3$ then any pair of faces has at most a single common boundary edge so $G** = G$. \end{proof} \begin{definition}[Plane map] A plane map is a plane graph together with its set of faces. \end{definition} \begin{definition}[Face colouring] A (face) colouring of a plane map is an assignment of colours to the faces of the map with the condition that faces sharing an edge have different colours. \end{definition} \begin{example} Let $G$ be a plane graph with every vertex of even degree. Then every face in the dual has an even number of sides. Therefore every cycle in the dual is even, so the dual is bipartite, so there is a face colouring of $G$ with just two colours. \end{example} \begin{definition}[Four colour conjecture] The four colour conjecture (4CC) asserts that every plane map can be 4-face coloured. Alternatively every plane graph has $\chi(G) \le 4$ by considering the dual. The 4CC was made popular by Cayley in 1878. Almost at once, ``proofs'' appeared: Kempe 1879, Tait 1880. \end{definition} \end{document}