Title: Part II / Graph Theory
Tags: Introduction Graph::Colouring Connectivity::and::Matchings Extremal::Graph::Theory Ramsey::Theory Algebraic::Methods Probabilistic::Method Bipartite::Graphs Planar::Graphs

Q: Definition. A graph is [...]
A: an ordered pair G = (V,E) of sets s.t. V is a set of vertices and E is a subset of the set \(V^{(2)} = \{(x,y) : x,y \in V, x \neq y\}\) of unordered pairs from V.

Q: Definition. The order of G is [...] and the size of G is [...]
A: \(|G|= |V(G)|\); \(e(G) = |E(G)| \)
Back Extra: The ends of an edge are incident with the edge

Q: Definition. Graphs \(G = (V,E), H = (V', E')\) are isomorphic if [...]
A: \(\exists \text{ bijection } f: V \to V'\) such that \(xy \in E \iff f(x)f(y) \in E'\)

Q: Definition. \(H = (V', E')\) is a subgraph of \(G = (V,E)\) if [...]
A: \( V' \subseteq V, E' \subseteq E \)

Q: Definition. We say \(x,y\) are adjacent or neighbours if [...]. The neighbourhood of x is [...]. The degree of x is [...]
A: \(xy \in E\); \(\Gamma (x) = \{y \in V : xy \in E\}\); \(d(x) = |\Gamma(x)|\)

Definition. If \(V(G) = \{x_1, \dots , x_n\}\) then the degree sequence of G is \(d(x_1), d(x_2), \dots, d(x_n)\). The maximum degree of G is \(\Delta (G) = \max_{1 \leq i \leq n} d(x_i)\). The minimum degree of G is \(\delta (G) = \min_{1 \leq i \leq n} d(x_i)\). G is regular of dgree k (or k-regular) if \(d(x) = k \; \; \forall x \in V\).

Q: Definition. In graph G, an x-y path is [...]. We say that G is connected if [...]
A: a sequence \(x_1, \dots , x_k\) of distinct vertices in G with \(x_1 = x, x_k = y\) and \(x_i x_{i+1} \in E \; \; \forall 1 \leq i \leq k-1\); \(\forall x,y \in V\) there is an x-y path in G.

Definition. Empty graph \(E_n\) is \(V = \{x_1, \dots x_n\}, E = \emptyset\). Path of length n \(P_n\) is \(V = \{x_1, \dots, x_{n+1}\}, E = \{x_1 x_2, \dots, x_n x_{n+1}\}\). Cycle \(C_n\) of length n \(n \geq 3\) is \(V = \{x_1, \dots ,x_n\}, E = \{x_i x_{i+1} : 1 \leq i \leq n-1\} \cup \{x_n x_1\}\). Complete n-graph \(K_n\) is \(V = \{x_1, \dots, x_n\}, E = V^{(2)}\)

Q: Lemma. If \(x \sim y \iff \exists x-y \text{ path in G}\) then \(\sim\) is an equivalence relation.
A: Reflexivity and symmetry are immediate. For transitivity if \(x_1 \dots x_l\) is a x-y path and \(y_1 \dots y_k\) is a y-z path then choose the minimal subsequence \(w_1 \dots w_r\)of \(x_1 \dots x_l y_1 \dots y_k\) such that \(w_i w_{i+1} \in E\) and \(w_1 = x, w_r = z\). We now claim that this is a x-z path. If not it has to fail on distinctness, so we have some p such that the sequence is \(w_1 \dots w_a p w_{a+2} \dots w_{b} p w_{b+2} \dots w_r\) but then \(w_1 \dots w_a p w_{b+2} \dots w_r\) satisfies the subsequence condition and is shorter. Contradiction.

Q: Definition. A graph G is said to be acyclic if [...]
A: it does not contain any subgraph isomorphic to a cycle, \(C_n\).
Back Extra: An acyclic graph is a forest. \[\text{G forest} \iff \text{every component of G is a tree}\]

Q: Definition. A tree is [...]
A: a connected, acyclic graph.

Q: Definition. Let G be a graph. A vertex \(v \in V(G)\) is a leaf [...]
A: if \(d(v) = 1\)

Q: Definition. Let G be a graph. We say T is a spanning tree of G if [...]
A: T is a tree on \(V(G)\) and is a subgraph of G.

Q: Definition. Call the ~ equivalence classes the [...] A walk is [...]
A: components of G.; an alternating sequence of veritces and edges.
Back Extra: \[\text{G has an x-y walk} \iff \text{G has an x-y path}\]

Q: Definition. In a tree T, a leaf( or endvertex) is [...]
A: a vertex with degree 1

Q: Proposition. Let G be a graph, TFAE
(a) G is a tree
(b) G is a maximal acyclic graph(adding any edge creates a cycle)
(c) G is a minimal connected graph(removing any edge disconnects graph)
A: (a) -> (b) By definition G is acylic. Let \(x,y \in V \text{ s.t. } xy \not \in E\). As G is connected \(\exists x-y\) path, P, in G. So \(G + xy\) contains the cycle \(Pyx\)
(b) -> (a) By definition G is acyclic. If G is not connected, let x,y be vertices from different components. Then G + xy is acylic. Contradiction
(a) -> (c) By definition G is connected. Suppose for contradiction \(\exists\) some vertices \(x,y, xy \in E, x \neq y\) such that G - xy is connected. Then \(\exists\) some x-y path, P that does not use the edge xy. Hence Pyx is a cycle in G
(c) -> (a) By definition G is connected. Assume for contradiction G contains a cycle C. Choose \(xy \in E(C)\). Claim G - xy is connected. Now, if \(a,b \in V(G - xy)\) let P be a path in G from a to b. If xy doesn't appear as consecutive vertices in this path, then a is connected to b. Otherwise, consider new pth, replacing x,y with the other vertices in C - xy in order. Thus a,b still connected. This contradicts minimality.

Q: Proposition. Every tree with \(|T| \geq 2\) has a leaf.
A: Given tree T, let P be a path of max length in T, say \(P = x_1 \dots x_k\)
Clearly \(d(x_k) \geq 1\) as \(x_k x_{k-1} \in E\). If \(x_k\) is adjacent to another vertex \(y \neq x_{k-1}\), either \(y \in \{x_1 , \dots, x_{k-2}\}\) in which case T contains a cycle or y is not in this set, in which case the original path was not of maximum length. Contradiction.

Q: Proposition. Let T be a tree on n(\(\geq 1\)) vertices. Then \(e(T) = n-1\). We write \(G[W]\) for the subgraph spanned by W.
A: If \(x \in V\), write G - x for \(G[V \setminus \{x\}]\). This definition coincides with the previous. To prove this we use induction on \(n = |T|\). If \(n = 1\), trivial. If T has n vertices then pick a leaf \(x \in T\), and define \(T' = T -x\). T' is a tree as it is acyclic since we've removed a vertex. It is connected since \(\forall a,b \in V(T') \; \exists\) path \(a \to b\) in T that doesn't use x so it's also a path in T'.
Now \(|T'| = n-1\) so by induction \(e(T) = e(T') + 1 = n-1\).

Q: Lemma. Every connected graph has a spanning tree.
A: A tree is a minimal connected graph. Take the connected graph and remove edges until it becomes a minimal connected graph. This is a subgraph of the original graph therefore it is a spanning tree.

Q: Definition. For G connected, \(xy \in E\) is bridge if [...]
A: \(G - xy\) is disconnected

Q: Definition. A graph is bipartite if [...]. The complete bipartite graph \(K_{n,m}\) has [...]
A: \(V = V_1 \cup V_2\) where \(V_1 \cup V_2 = \emptyset\) and all edges \(xy \in E\) have either \(x \in V_1, y \in V_2\) or \(x \in V_2, y \in V_1\); \(|V_1| = n, |V_2| = m\) with \(E = \{xy : x \in V_1, y \in V_2\}\) so \(e(K_{n,m}) = nm\)

Q: Proposition. The cycle \(C_{2k+1}\) is not bipartite and the cycle \(C_{2k}\) is bipartite.
A: If \(C_{2k+1}\) is bipartite \(\exists\) disjoint sets \(V_1, V_2\) and as 2k+1 is odd, we must WLOG \(|V_1| > |V_2|\). Counting edges between \(V_1\) and \(V_2\), this number of edges must be \(2|V_1|\) and \(2|V_2|\) as every vertex has degree 2. So \(|V_1| = |V_2|\). Contradiction
Consider \(C_{2k}\). Let \(x_i \in V_1\) if i is even, \(x_i \in V_2\) if i is odd. Then vertex \(x_i\) only has edges to vertices whose indices have opposite parity so we are done.

Q: Definition. A circuit in G is [...] If the length of the circuit is odd we say it is an odd circuit.
A: a closed walk \(x_1 \dots x_k\) where \(x_1 = x_k\) and \(x_i x_{i+1} \in E\). Its length is k-1.

Q: Lemma. An odd circuit contains an odd cycle.
A: Induction on length of circuit. If length is 3, circuit is a cycle. In general let \(C = x_1 \dots x_k\) be citcuit. If \(x_1, \dots , x_k\) are distinct then C is cycle and we are done. If not \(\exists z \in C\) that is repeated. Write \[C : x_1 \dots x_a z x_{a+2} \dots x_b z x_{b+2} \dots x_k\]Define \(C' : x_1 \dots x_a z x_{b+2} \dots x_k\) and \(C'' : zx_{a+2} \dots x_b z\). Lengths of C', C'' are strictly less than that of C. One of them has odd length and by induction that odd circuit contains an odd cycle.

Q: Proposition. A graph G is bipartite iff G has no odd cycle.
A: If G is bipartite and contained an odd cycle, then \(\exists\) odd cycle that is bipartite. Contradiction.
If G is not bipartite, we induction on number of vertices. \(|G| = 1\) clear. If not connected, let \(D_1 , \dots , D_n\) be components of G. Apply induction to each component of G to obtain a bipartition \(V(D_i) = W_i \cup W_i'\).Then \(V_1 = W_1 \cup \dots \cup X_n\) and \(V_2 = W_1' \cup \dots \cup W_n'\) is bipartition for the whole graph. So WLOG G is connected. Fix \(x_1 \in V\). Define \(V_1 = \{x \in V: d(x,x_1) \text{ odd }\}\), \(V_2 = \{x \in V : d(x, x_1) \text{ even}\}\)
Claim: \(V_1 \cup V_2\) is bipartition. Assume for contradiction x adjacent to y and \(d(x, x_1) \equiv d(y, x_1) \mod 2\). Then \(\exists\) paths \(P_1\) from \(x_1\) to \(x\) and \(P_2\) from \(y\) to \(x_1\) with \(|P_1| \equiv |P_2| \mod 2\). This means \(x_1 P_1 xy P_2\) defines as odd circuit in G. Therefore G contains an odd cycle, contradiction.

Q: Definition. A planar graph [...]
A: can be drawn on the plane without any pair of edges crossing. A plane graph is such a drawing.

Q: Definition. The faces of a plane graph G are [...] The boundary of a face consists of [...]
A: the connected components of \(\mathbb{R}^2 - G\).; the vertices and edges that touch it

Q: Definition. Let \(x,y \in \mathbb{R}^2, x \neq y\). A polygonal arc from x to y is [...] For graph G, \(V(G) = \{v_1 , \dots , v_n\}\), a drawing of G consists of [...]
A: a finite union of straight line segements \(\overline{x_1 x_2} \cup \dots \cup \overline{x_{n-1}x_n}\) with \(x_1 = x, x_n = y\) that are disjoint except from; distinct points \(x_1 , \dots, x_n \in \mathbb{R}^2\) together with, for each edge \(v_i, v_j \in E\), a polygonal arc \(p_{ij}\) from \(x_i\) to \(x_j\) s.t. \(p_{ij} \cap p_{kl} = \emptyset\) if i,j,k,l distinct and \(P_{ij} \cap P_{jk} = \{x_j\}\)
Back Extra: For \(x,y \in \mathbb{R}^2 - G\), \(x \sim y\) if \(\exists\) polygonal arc in \(\mathbb{R}^2 - G\) from x to y. The components are called faces. The boundary of a face consists of G \(\cap\) its closure.

Q: Theorem. Euler's Formula. Let G be a connected plane graph with n vertices, e edges and f faces. Then \[n - e + f = 2\]
A: Induction on number of edges. \(e = 0\). Since G is connected, n=1 so formula holds.
For \(e>0\). If G contains a cycle C, then let edge \(e'\) be on C. Then \(G' = G - e'\) is still connected and the number of faces decreases by 1. So considering \(G'\) and applying the formula \[n - (e-1) + (f-1) = 2\]If G has no cycles it is a tree so \(e = n-1, f = 1\) and the result holds.

Q: Corollary. Let \(G = (V,E)\) be a plane graph with \(n \geq 3\). Then \(e \leq 3n - 6\)
A: WLOG G is connected, otherwise add edges until it is. Draw G in the plane so that there are no edge crossings. Then we know \(n - e + f = 2\). Every face has \(\geq 3\) edges on its boundary and every edge is incident to \(\leq 2\) faces. Therefore by counting the number of edges on each face we get\[3f \leq 2e\]Plugging into Euler's formula gives us the result.

Definition. A subdivision of a graph G is a graph \(\hat{G}\) obtained by replacing the edges of G with disjoint paths.

Q: Lemma. G is non-planar \(\implies\) a subdivision of G is non-planar too
A: Given a plane drawing of a subdivided graph, by disregarding the vertices on subdivided paths you obtain a plane drawing of G

Q: Corollary. Subdivisions of \(K_5\) and \(K_{3,3}\) are non-planar
A: Use the bound on edges to vertices using a better bound for a bipartite graph

Q: Theorem. Kuratowski. A graph is planar iff G contains no subdivisions of \(K_5\) or \(K_{3,3}\)
A: No proof.

Q: Definition. A set of edges is independent if [...] A matching from X to Y consists of [...] A matching of deficiency d [...]
A: none of its edges have any vertex in common.; \(|X|\) independent edges.; has \(|X| - d\) independent edges.

Q: Theorem. Hall's Marriage. Let G be a bipartite graph with vertex classes X,Y. Then G has a matching from X to Y iff \[|\Gamma(A)| \geq |A|\]\(\forall A \subseteq X\)
A: (-->) \(A = \{x_1 , \dots, x_r\} \subseteq X\). Matching edges \(x_1y_1, \dots ,x_ry_r \in E\). Then \(\{y_1 , \dots , y_r\} \subseteq \Gamma(A) \) so \(|\Gamma(A)| \geq |A|\)
(<--) Induction on \(|X|\), noting \(|X| = 1\) clear. Given G, \(|X| > 1\) such that \(|\Gamma(A)| \geq |A| \; \; \forall A \subseteq X\). Assume every bipartite graph on classes \(X' , Y'\) with \(|X'| < |X| \) satisfying Hall's condition has a matching X' to Y'/
Case 1: \(\forall \emptyset \geq A \not \subseteq X, |\Gamma(A)| > |A|\). Take \(x \in X, y \in \Gamma(x)\) and let \(G' = G - x - y\). Then \(\forall A \subseteq X \setminus \{x\}\) \[|\Gamma_{G'}(A)| \geq |\Gamma_G(A)| -1 \geq |A|\]as \(|\Gamma_G(A)| \geq |A| + 1\). Induction provides a matching in G' of \(X \setminus\{x\}\) to \(Y \setminus \{y\}\) Together with xy we get a matching from X to Y
Case 2: \(\exists \emptyset \neq A \not \subseteq X\) with \(|\Gamma(A)| = |A|\). Let \(\Gamma(A) = B\). Let \(G_1 = G[A \cup B], G_2 = G[(X \setminus A) \cup (Y \setminus B)]\) both bipartite.
Claim 1: \(G_1\) has a matching from A to B. For \(C \subseteq A, |\Gamma_G(C)| \geq |C|\), have \(|\Gamma_{G_1}(C)| \geq C\) since \(\Gamma_{G_1}(C) = \Gamma_G(C)\) so by induction \(G_1\) has a matching from A to B
Claim 2: \(G_2\) has matching from \(X \setminus A\) to \(Y \setminus B\).
For \(C \subseteq X \setminus A\), \(|\Gamma_G(C \cup A)| \geq |C| + |A|\) as \(\Gamma_G(C \cup A) = \Gamma_G(A) \cup \Gamma_{G_2}(C)\)
So \(\Gamma_G(C \cup A)\) contains \(\geq |C|\) points of \(Y \setminus B\) as \(\Gamma(A)= B, |B| = |A|\).
Now \(\Gamma_G(A)\) is disjoint from \(Y \setminus B\) therefore \(|\Gamma_{G_2}(C)| \geq |C| \) as \(\Gamma_{G_2}(A \cup C) \setminus \Gamma_G(A)\)
So by induction \(G_2\) has matching from \(X \setminus A\) to \(Y \setminus B\). Putting the two matchings together gives G a matching from X to Y.

Q: Corollary. Let G be a bipartite graph with vertex classes X,Y. Then G has a matching of deficiency d from X to Y iff \[|\Gamma(A)| \geq |A| - d \; \; \; \forall A \subseteq X\]
A: \(\implies\)is clear
\(\impliedby\) Form \(G'\) adding d new points to Y, each joined to all of X. Then \(|\Gamma_{G'}(A)| \geq |A|\) for all subsets A so by Hall's theorem there is a matching in G', which will be a matching of deficiency d in G.

Q: Corollary. Sets \(S_1 , \dots , S_n\) have a transversal iff \[|\bigcup_{i \in A} S_i| \geq |A| \; \; \forall A \subseteq \{1, \dots, n\}\]
A: \(\implies\)is clear
\(\impliedby\) construct a bipartite graph as follows: \(X = \{1 , \dots ,n\}, Y = S_1 \cup \dots \cup S_n, i \in X\) is joined to \(j \in Y\) if \(j \in S_i\). So transversal is a matching from X to Y. If \(A \subseteq X, |\bigcup_{i \in A} S_i| \geq |A|\), i.e. \(|\Gamma(A)| \geq |A| \) so we're done by Hall.

Q: Definition. For a graph G \(|G| > 1\), the connectivity of G, \(\kappa(G)\), is the [...] \[[...]\]
A: least size of a set \(S \subseteq V\) s.t. \(G - S\) is disconnected, or a single point; G \text{ is k-connected if } \kappa(G) \geq k
Back Extra: So G is k-connected \(\iff |G| > k\) and no set of size \(< k\) disconnects G

Q: We have the following equivalences\[1-\text{connected} \iff [...]\]
\[2-\text{connected} \iff[...]\]
\[3 - \text{connected} \iff [...]\]
A: G \text{ is connected} (|G|> 1); G \text{ has no cutvertex}(|G| > 2); G \text{ cannot be disconnected by removing two vertices}

Q: Definition. Consider a,b distinct vertices of G. Say \(S \subseteq V(G) \setminus \{a,b\}\) seperates a from b or S is an a-b seperator if [...]
A: a,b are in different components of G - S, i.e. every a-b path meets S

Q: Theorem. Menger's. Let G be graph, and a,b non-adjacent vertices of G. If all a-b seperators have size \(\ge k\) then there exists a family of k independent \(a-b\) paths.
A: WLOG assume \(k \ge 2\)(k=1 is clear). Now k = min size of a-b seperator. Seek k independent paths from a to b.
If it's not possible, consider a minimal counterexample(minimises k and minimises the number of edges of graph)
Let S be an a-b seperator, \(|S| = k\). Two cases:
(1) Suppose for \(S \neq \Gamma(a), S \neq \Gamma(b)\). Form G' from G by replacing the component of \(G - S\) containing a by a single point a' joined to everything in S. Then \(e(G') < e(G)\) (otherwise \(\Gamma(a) \subseteq S\)), have \(\Gamma(a) = S\). In G' there is no  \(a' - b\) seperator of size \(< k\). Otherwise the same set seperates a and b in G. So by minimality of \(e(G)\) \(\exists k\) independent a'-b paths in \(G'\). Hence have \(k\) paths \(P_1, \dots , P_k\) from b to S disjoint except at b. Similarly k paths \(Q_1 , \dots , Q_k\) from a to S disjoint except at a.
No \(Q_i\) can meet \(P_j\) except on S(as S is a seperator), so put the \(Q_i, P_j\) together to form k independent a-b paths in G. Impossible.
(2)Suppose now any a-b seperator S of size k has \(S = \Gamma(a)\) or \(S = \Gamma(b)\). Observe that \(\Gamma(a) \cap \Gamma(b) = \emptyset\): if \(x \in \Gamma(a) \cap \Gamma(b)\), consider \(G' = G - x\). All a-b seperators in \(G'\) have size \(\ge k-1\)(as, with x, they seperator a from b in G). By minimality of k, \(\exists k-1\) independent a-b paths in G'. Now add the path axb to obtain k independent a-b paths in G. Impossible.
Consdier a shortest path \(a x_1 \dots x_r b\)\((r \geq 2)\) from a to b. Let \(G' = G - x_1 x_2\). In this G', there exists a seperator S of size k-1 by minimality.
Note \(S \neq \emptyset\) as \(k \geq 2\). Then \(S \cup \{x_1\}, S \cup \{x_2\}\) are seperators in G of size k. As \(x_1 \not \in \Gamma(b), S \cup \{x_1\} \neq \Gamma(b)\). As \(x_2 \not \in \Gamma(a), S \cup \{x_2\} \neq \Gamma(a)\). Hence \(S \cup \{x_1\} = \Gamma(a), S \cup \{x_2\} = \Gamma(b)\), contradicting \(\Gamma(a) \cap \Gamma(b) = \emptyset\)

Q: Corollary. 'vertex version' of Mengers. Let G be a graph, \(|G| > 1\). Then G is k-connected iff \(\forall \) distinct \(a,b \in G\) G has k independent a-b paths.
A: (\(\impliedby\))Certainly G is connected and \(|G| > k\). Also for \(|S| \leq k-1\), \(G - S\) is connected (otherwise pick a,b in different components of \(G - S\))
(\(\implies\))a,b non-adjacent \(\implies\)use Menger's theorem (as G k-connected, no set of size \(< k\) can seperator a,b). a,b adjacent \(\implies G' = G - ab\). Then G is (k-1)-connected as G is k-connected. So by Menger's theorem \(\exists k-1\) independent a-b paths in G' (no a-b seperator in G' has size \(< k-1\)). Now add edge ab to obtain k independent a-b paths in G.

Q: Definition. For G connected, \(|G| > 1\), define the edge connectivity of G, \(\lambda(G)\), to be [...] Say G is k-edge connected if \(\lambda(G) \geq k\)
A: smallest \(|S|\) with \(S \subseteq E(G)\) s.t. \(G - S\) is disconnected.

Q: Definition. For a graph G, the line graph \(L(G)\) has [...]
A: vertex set \(E(G)\) with e,f joined if they share a vertex.

Q: Theorem.'edge version' of Menger. Let G be a graph and \(a \neq b \in V\). Then the min size of a set \(S \subseteq E\) seperating a from b equals the max number of edge-disjoint a-b paths.
A: From G' from L(G) by addint two points a',b', with a' joined to each \(e \in E\) incident with a, similarly for b'.
Then \(\exists a-b\) path in G iff \(\exists a'-b'\) path in G'. Moreover a family of k independent \(a'-b'\) paths in G' gives a family of k edge-disjoint a-b paths in G. Done by the vertex version of Menger applied to \(G'\)

Q: Corollary. Let G be a graph, \(|G| >1\). Then G is k-edge connected iff \(\forall\) distinct a,b \(\exists \)k-edge disjoint a-b paths.
A: \(\implies\)is the edge version of Menger
\(\impliedby\)is clear

Q: Definition. An Euler(or Eulerian) circuit in a graph G is [...] Call G Eulerian if [...]
A: a circuit passing through each edge exactly once.; it has an Euler circuit.

Q: Theorem. Euler's. A connected graph has an Eulerian circuit iff every vertex has even degree
A: (\(\implies\)) If an Eulerian circuit passes through x k times, then \(d(x) = 2k\).
(\(\impliedby\))Induction on \(e(G) > 0\) and \(d(x)\) even \(\forall x \in G\). Suppose G is not Eulerian and let \(C\) be the longest circuit in G with no edges repeated. Note \(e(C) > 0\) as G has a cycle (since \(d(x) \ge 2 \forall x \in G\) so G is not a tree) Assume \(E(C) \neq E(G)\). Let H be a component of \(G - E(C)\) with \(e(H) > 0\). Then H is connected \(d_H(x)\) is even \(\forall x \in H\)(as \(d_G(x)\) is even, \(d_C(x)\) is even). By induction H gas to have an Euler circuit C', say. Now \(C',C\) are edge disjoint circuits that share a vertex(note \(V(H) \cap V(C) \neq \emptyset\) as G connected)
Hence can combine C', C to form a circuit longer than C with no repeated edge.

Q: Definition. Let G be a graph. A Hamilton cycle in G is [...] We say G is Hamiltonian if [...]
A: a cycle that visits each vertex exactly once.; it contains a Hamilton cycle.

Q: Theorem. Every graph of order \(n \ge 3\) and \(\delta(G) \geq n/2\) is Hamiltonian.
A: Assume G is a counter example.
Note G is connected, if x,y non-adjacent \(\Gamma(x), \Gamma(y) \subseteq V \setminus \{x,y\}\) and \(|\Gamma(x)|, |\Gamma(y)| \ge n/2\) therefore \(\Gamma(x) \cap \Gamma(y) \neq \emptyset\)
Let \(P:x_1 \dots x_l\) be longest path in G. So \(l \ge 3\). Note C does not have an \(l\)-cycle. Otherwse, if l =n we're done and if \(l < n\), then as G is connected \(\exists x \not \in\) cycle adjacent to some \(y \in \) cycle, giving a path on l+1 points, contradiction.
So \(x_lx_1 \not \in E\). If \(\exists i \in \{1, \dots, l-1\}\) s.t. \(\exists x_i - x_l\) path and \(x_{i+1}-x_1\) path, then \(x_1 , \dots , x_l\) forms a cycle
Define \(\Gamma^+ (x_l) = \{x_i : x_{i-1} \in \Gamma(x_l) : 2 \le i \le l\}\). \(\Gamma^+(x_l) \cap \Gamma (x_1) = \emptyset\). This is impossible as \(|\Gamma^+(x_l) \geq n/2|, |\Gamma(x_1)| \geq n/2\) and \(\Gamma^+(x_l), \Gamma(x_1) \subset \{x_2 , \dots , x_l\}\)(by maximality of path).

Q: Lemma. Let G be a connected graph of order n(\(\ge 3\)) and \(\delta(G) \ge k/2\) for some integer \(k < n\). Then \(P_k \subseteq G\)
A: Suppose no path of length k. Let \(P: x_0 x_1 \dots x_l\) be a path of max length \(l < k\). By maximality, neightbours of \(x_0, x_l\) must all be inside P. Let \[A = \Gamma(x_0), B = \{x_{i+1}: x_i \in \Gamma(x_l)\}\]Since \(\delta(G) \ge k/2\), \(|A|, |B| \ge k/2\). Also \(x_0 \not \in A, x_0 \not \in B\) hence \(A \cap B \subseteq \{x_1 , \dots , x_l\}.\) So \(|A\cup B| \leq l < k\). This forces \(A \cap B \neq \emptyset\), otherwise \(|A \cup B| \geq k/2 + k/2 = k\)
Suppose \(\exists i\) s.t. \(x_i \in A \cap B\). Consider cycle C of length l: \[C : x_0 - x_i - x_{i+1} - \dots - x_{l-1} - x_l - x_{i-1} - x_{i-2} - \dots - x_2 - x_0\]Since \(l < k < n\) we can now construct path P' of length \(\ge l+1\). As \(l<n\) \(\exists\) at least one vertex \(c \not \in C\). As G connected \(\exists\) path from c to some vertex \(x_j \in C\). To get P' start from c to \(x_j\) and then traverse C to \(x_{j-1}\). Length of P' is at least l+1. Contradiction

Q: Theorem. Let G be a graph on n(\(\ge 3\)) points. Then \[e(G) > \frac{n(k-1)}{2} \implies P_k \subseteq G\]Equivalently: \(P_k \not \subseteq G \implies e(G) \leq \frac{n(k-1)}{2}\)
Best possible is taking n/k copies of complete k-graph
A: k=1 means no possible edge in G and so \(e(G) = 0\). Assume \(k \geq 2\) and use induction on n. Base case \(n \le k\), clear as \(e(G) \le {n \choose 2} = \frac{n(n-1)}{2} = \frac{n(k-1)}{2}\)
WLOG, G is connected: if G is disconnected with components \(C_1, \dots , C_r\) on \(n_1 , \dots , n_r\) vertices respectively.
\(P_k \not \subseteq C_i\) so \(e(C_i) \le \frac{n_i(k-1)}{2}\) by induction. Therefore \(e(G) = \sum_i e(C_i) \leq \sum \frac{n_i(k-1)}{2} = \frac{n(k-1)}{2}\)
By (3.5) \(\exists \)vertex x of degree \(\le \frac{k-1}{2}\). Let \(G' = G - x\), graph on n-1 vertices and \(P_k \not \subseteq G\) therefore \(e(G') \le \frac{(n-1)(k-1)}{2}\)\[e(G) \le e(G') + \frac{k-1}{2} = \frac{n(k-1)}{2}\]

Q: Definition. Say G is r-partite if[...]
A: \(\exists\) partition \(V = V_1 \cup \dots \cup V_r\) of V s.t. \(V_i \cap V_j = \emptyset\)(\(1 \leq i < j \le r\)) and \(xy \not \in E\) \(\forall x,y \in V_i\)(no edge joins two vertices in the same class)

Q: Definition. Complete r-partite graph.[...]
A: If no edge can be added with the graph remaining r-partite \[E(G) = \{xy, x \in V_i, y \in V_j, i \neq j\}\]

Q: Definition. The Turán graph \(T_r(n)\) is [...]
A: the complete r-partite graph on n vertices, with vertex classes \(V_1, \dots , V_r\) with \(|V_1|, \dots , |V_r|\) as equal as possible.

Q: Theorem. Turán's. Let G be a graph on n vertices. If \(e(G) > e(T_{r-1}(n))\) then \(K_r \subseteq G\)
A: We prove that \(|G|= n, e(G) = e(T_{r-1}(n)), K_r \not \subseteq G \implies G \cong T_{r-1}(n)\)(which implies statement, by maximality of \(T_{r-1}(n)\))
We use induction on n. For \(n \le r-1\) clear.
Assume \(n \ge r\) we're assuming \(|G| = n, e(G) = e(T_{r-1}(n))\), \(K_r \not \subseteq G\)
Claim: \(\delta(G) \le \delta(T_{r-1}(n))\)
Now \(e(G) = e(T_{r-1}(n))\) therefore \(\sum_{y \in G} d_G(y) = \sum_{y \in T_{r-1}(n)} d_{T_{r-1}(n)}(y)\)
As the \(d_{T_{r-1}}\) are as equal as possible, \(\delta(G) \le \delta(T_{r-1}(n))\)
Claim 2: Choose \(x \in G, d(x) = \delta(G)\) and let \(G' =G - x\). Then \(G' = T_{r-1}(n-1)\)
\(|G'| = n-1, K_r \not \subseteq G'\) and \(e(G') = e(G) - \delta(G) \ge e(T_{r-1}(n)) - \delta(T_{r-1}(n)) = e(T_{r-1}(n-1))\)
So \(G' \cong T_{r-1}(n-1)\) by induction hypothesis \(\delta(G) = \delta(T){r-1}(n))\)
Finally let \(V_1 , \dots , V_{r-1}\) be vertex classes of G'.
Observe that \(\Gamma(x)\) misses some \(V_i\)(otherwise \(K_r \subseteq G\)) so \(\Gamma(x) \cap V_i = \emptyset \) for some i
But \(|\Gamma(x)| = d(x) = n-1 - \min |V_i|\)
Hence \[\Gamma(x) = \bigcup_{j \neq i} V_j\]for some i s.t. \(|V_i|\) is minimal.
Therefore G is complete \(r-1\)-partite with vertex classes \(V_j(j \neq i)\) and \(V_i \cup \{x\}\). Thus \(G \cong T_{r-1}(n)\)

Q: Definition. Z(n,t) is [...]
A: the max number of edges on a bipartite graph with n vertices in each class if it does not contain \(K_{t,t}\)

Q: Theorem. Let \(t \ge 2\). Then \(Z(n,t) \le 2n^{2 - \frac{1}{t}}\) for all sufficiently large n
A: \(G = (X \cup Y, E),|X| = |Y| = n\) bipartite graph, \(K_{t,t} \not \subseteq G\)
List the degrees in X: \(d_1 , \dots , d_n\). WLOG \(d_i \ge t-1\) for all i otherwise we can add edges to that vertex to make \(d_i = t-1\)
For each t-set \(S \subseteq Y\), we count how many \(x \in X\) have \(S \subseteq \Gamma(x)\)
Evidently it must be \(\le t-1\) as \(K_{t,t} \not \subseteq G\)
Thus the number of \((x,S)\) with \(x \in X, S \subseteq Y, |S| = t\) and \(S \subseteq \Gamma(x)\) is \(\le (t-1) {n \choose t}\)
Now each \(x \in X\) belong to exactly \(d(x) \choose t\) such \((x,S)\).
Therefore \[\sum {d_i \choose t} \le (t-1) {n \choose t}\]
Consider \(x \choose t\) as a convex function of x.
Thus \[\sum {d_i \choose t} \ge n {d \choose t}\]where d is the average of \(d_i\). Remembering that \(e(G) = nd\)
\(\frac{n(d-t+1)^t}{t!} \le \frac{(t-1)n^t}{t!} \implies d \le (t-1)^{1/t}n^{1 - 1/t} + t - 1 \implies nd = e(G) \le t^{1/t} n^{2-1/t} + tn\)

Q: Definition. An r-colouring of \(G = (V,E)\) is [...] The chromatic number \(\chi(G)\) is [...]
A: a function \(c: V \to [r]\) that satisfies \(xy \in E \implies c(x) \neq c(y)\); the smallest r s.t. G has an r-colouring.

Q: Lemma. \[G \text{ bipartite} \iff \chi(G) \le 2\]
A: Fairly trivial

Q: Definition. Given \(G = (V,E)\) with vertices \(\{v_1 , \dots , v_n\}\), the greedy colouring of G on an ordering \(v_1 , \dots , v_n\) is defined as
[...]
A: 1) Colour them one by one, with \(c(v_1) = 1\)
2) Then give \(v_2\) colour 1 if \(v_1 v_2 \not \in E\) and colour 2 otherwise
3)Repeat, colouring each vertex with the smallest colour it can have

Q: Proposition. For any graph G, we have \[\chi(G) \le \Delta(G) + 1\]
A: Order \[V: v_1 , \dots, v_n\] and colour them in turn using the greedy colouring. When you colour \(v_i\) it has \(\le \Delta\) neighbours, and we have \(\le \Delta\) colours to avoid and have \(\ge 1\) to use.

Q: Theorem. 6-Colour Theorem. \[G \text{ planar} \implies \chi(G) \leq 6\]
A: Clear if \(|G| \le 6\). Assume \(n = |G| \ge 7\)
Observe \(\delta(G) \le 5\). Note \(e(G)\le 3n - 6\), so \[\frac{1}{n}(\sum_{x \in V} d(x))\le 6 - \frac{12}{n} < 6\]therefore \(\exists x\) s.t. \(d(x) \le 5\)
Pick \(x \in G, d(x) \le 5\) and let \(G' = G - x\). Can 6-colour \(G'\) by induction on n. Now \(d(x) \le 5\), \(|\Gamma(x)| \le 5\) so \(\Gamma(x)\) has less than 5 colours so colour x with the 6th.

Q: Definition. Given G and r-colouring of G, let \(x \in V(G)\) and define i-j component of x to be [...]
A: all of the vertices that can be reached starting at x along a path using only colours i,j.

Q: Lemma. Given G and r-colouring, and for i,j colours, we can swap the colours on i-j component to obtain a new colouring.
A: Clear.

Q: Theorem. 5-Colour Theorem. \[G \text{ planar} \implies \chi(G) \le 5\]
A: Induction on \(|G|, |G| \le 5\) clear. Given \(G,|G| \ge 6\) and again \(\exists x\) with \(d(x) \le 5\).
Remove it. By induction , we can \(5-\)colour G-x. We can now colour x, unless \(d(x) = 5\) and all colours appear in \(\Gamma(x)\). Let \(\Gamma(x) = \{x_1, x_2, x_3,x_4, x_5\}\) arranged clockwise with \(x_i\) colour i \(\forall i\)Suppose there is no 1-3 path from \(x_3\) to \(x_1\)(this is a path that alternates between colours 1 and 3). Let H be the 1-3 component of \(x_3\). Then \(x_1 \not \in H\). Flip the colours 1,3 on H.
By this is a colouring of G-x and can now use colour 3 for x.
If \(\exists 1-3\) path from \(x_3 \to x_1\), there there is no 2-4 path from \(x_2\) from \(x_4\). Otherwise it would meet the 1-3 path from \(x_1\) to \(x_3\), as the drawing is planar, this can't happen.
Even if the paths go other way round, we see that in any of the cases they must intersect.
By the same argument as before, swap 2-4 component of \(x_2\), leaving 2 as a colour for \(x_1\).

Q: Theorem. Brooks's Theorem. Let G be a connected graph, not a complete graph or an odd cycle. Then \[\chi(G) \le \Delta\]
A: Let \( G \) be a counterexample with a minimal number of edges. We may assume \( G \) is a regular graph (\( \Delta \)-regular), and also that \( \Delta \geq 3 \).
Since \( G \) is not complete, there exists a vertex \( v \) so that \( G[N(v)] \) is not complete, so let \( x, y \in N(v) \) where \( x \not\sim y \). Colour these two vertices \( x, y \) the same colour.
If \( G \) is 3-connected then \( G' = G - x - y \) is connected. In this case, we order the vertices of \( G' \), labelled \( v_3, \dots, v_n = v \) so that
\[d_{G'}(v_3, v) \geq d_{G'}(v_4, v) \geq \dots \geq d_{G'}(v_{n-1}, v).\]
The greedy colouring with the ordering \( v_3, \dots, v_n \) will give us a \( \Delta \)-colouring of \( G \). Additionally, it’s possible to ensure that each \( w \in G' \) adjacent to either \( v_1 \) or \( v_2 \) is coloured differently from their common colour (check!). The key idea is that keeping \( G' \) connected allows the sequence of decreasing distances to be constructed.
If \( G \) has a cut vertex \( w \in V \), then let \( G - w = C_1 \cup \dots \cup C_k \) be the components, and \( G_i = G[C_i \cup \{w\}] \). The maximum degree in \( G_i \) is bounded by \( \Delta \), and therefore \( G_i \) has a \( \Delta \)-colouring for each \( i \), by the minimality of the counterexample. Note that \( G_i \) cannot be a complete graph on \( \Delta + 1 \) vertices since \( d_{G_i}(w) \leq \Delta - 1 \). By permuting the colours, we can assume each colouring gives the vertex \( w \) colour 1. Thus we have a colouring of \( G \) with \( \Delta \) colours, which is a contradiction.
If \( G - \{w_1, w_2\} \) is disconnected for \( w_1 \neq w_2 \) with \( w_1, w_2 \in V \), then let \( C_1, \dots, C_k \) be the components of \( G - \{w_1, w_2\} \). We may assume that \( G \) has no cut vertex by the previous case. Now let \( G_i = G[C_i \cup \{w_1, w_2\}] + w_1w_2 \). Note that \( e(G_i) < e(G) \) since \( w_1, w_2 \) both send at least one edge to each component \( C_1, \dots, C_k \). Also \( d_{G_i}(w_1) \leq \Delta \) and likewise \( d_{G_i}(w_2) \leq \Delta \), thus the maximum degree \( G_i \leq \Delta \) and thus we can find a \( \Delta \)-colouring of \( G_i \) for each \( i \). That gives \( w_1, w_2 \) different colours. After permuting these colours, I can assume \( w_1 \) is coloured 1 in each, and \( w_2 \) is coloured 2 in each. Thus we can put all of the colourings together to obtain a colouring of \( G \). \(\square\)

Q: Definition. For \(t \in \mathbb{N}\) and a graph G, write \(P_G(t)\) for [...]
A: the number of colourings of G with colours 1,2,...,t.
Back Extra: By definition, \(\chi(G)\) is the least t s.t. \(P_G(t) \ge 1\).

Q: Lemma. (deletion-contraction or cut-fuse relation). Let G be a grpah, \(e \in E\). Then \(P_G = P_{G=e} - P_{G /e}\)
A: \(e = xy\)
t-colourings of G-e s.t. x,y have different colours <--> t-colourings of G
t-colourings of G-e s.t. x,y get same colours <--> t-colourings of G/e
Hence \(P_{G-e}(t) = P_G(t) + P_{G/e}(t) \; \; \forall t\)

Q: Proposition. \(P_G(t)\) is a polynomial in t
A: Induction on e(G). \(P_{E_n}(t) = t^n\)
\(e(G)=0\) is done
Given G, \(e(G) > 0\), pick \(e \in E\).
Thus \(P_{G - e}, P_{G/e}\) are polynomials by induction
Therefore \(P_G = P_{G-e} - P_{G/e}\) is a polynomial

Q: Proposition. If G is a graph on n vertices, m edges, then the leading terms of \(P_G(t)\) are \(t^n - mt^{n-1} + \dots\)
A: Induction on \(e(G)\). Now \(P_{E_n}(t) = t^n\) therefore \(e(G) = 0\) is clear
Given G, \(e(G) > 0\), choose \(e \in E\). By induction \[P_{G - e} = t^n - (m-1)t^{n-1}\]\[P_{G / e} = t^{n-1} + \dots\]therefore \[P_G(t) = t^n - mt^{n-1} + \dots\]

Q: Definition. Let G be a graph. A k-edge colouring of G is [...]
A: a map \(c: E \to [k]\) s.t. \(c(e) \neq c(f)\) whenever \(e \neq f, e\cap f \neq \emptyset\)
Back Extra: An edge colouring of G is a vertex colouring of L(G).

Q: Definition. The edge-chromatic number or chromatic index of G is[...]
A: \(\chi'(G) = \text{minimum k for which a k-edge colouring exists}\)

Q: Theorem. Vizing's. For any graph G, \(\chi'(G) = \Delta(G) \) or \(\Delta(G) + 1\)
A: Induction on \(e(G),\) where \(e(G) = 0\) is trivial.
Must show \(\chi'(G) \le \Delta + 1\) i.e. that G can be \(\Delta + 1\) -edge coloured
Given G, \(e(G) > 0\), pick \(e \in E\). By induction \(\exists (\Delta + 1)\)-edge coluring of \(G - e\)
Write \(e = xy_1 (x \neq y_1)\). At each vertex, some colour is not being used (\(\# \)colours > max degree).
Say the colour \(c\) at \(x\) and \(c_1\) at \(y_1\). WLOG \(c \neq c_1\)
Choose maximal sequence of distinct vertices \(y_1 , y_2 , \dots , y_k\) all are neighbours of x such that some colour \(c_i\) is missing at \(y_i\) and \(xy_i\) has got colour \(c_i - 1(2 \leq i \leq k)\)
This exists as the graph is finite. it must terminate at \(y_k\) because either \(c_k\) does not occur at \(x\) or \(c_k = c_j\) for some \(j < k\).
If \(c_k\) does not occur at x, give \(xy_i\) colour \(c_i (1 \le i \le k)\), giving a \((\Delta + 1)\)-edge colouring of G.
If \(c_k = c_j(j < k)\) then WLOG \(j = 1\), by giving the edge \(xy_i(1 \leq i < j)\) colour \(c_i\) leaving \(xy_j\) as the uncoloured edge.
Let \(c\) be a colour not used at \(x\).
If  no \(c-c_1\) path from \(y_1\) to \(x\), swap colours \(c\) and \(c_1\) on \(c-c_1 \) component of \(y_1\)
Now c is missing at \(y_1\)(by our swap) and c is still missing at x, so you can colouring \(xy_1\) with colour c.
If no \(c-c_1\) path from \(y_k\) to \(x\). Swap colours \(c,c_1\) on the \(c-c_1\) component of \(y_k\). Now c is missing at \(y_k\) and at \(x\).
You are done, by giving \(xy_i\) colour \(c_i(1 \leq i \leq k-1)\) and giving \(xy_k\) colour c.
We may assume both. \(\exists c-c_1\) path \(y_1 \to x\) and also \(\exists c-c_1\) path from \(y_k \to x\)
Let H be the \(c-c_1\) component of \(x\) containing \(y_1, y_k\). Then \(\Delta(H) \leq 2\)(H is 2-edge coloured)
and H is connected, so H comprises paths or cycles. But \(d_H(x), d_H(y_1), d_H(y_k) \leq 1\)
Contradiction, as they can't all lie in the same component as a path has only two ends.

Q: Theorem. For any graph on a surface of genus g, \[n-m+f \geq 2 -2g\]
A: Proof omitted

Q: Theorem. Heawood. Let G be a graph drawn on a surface of Euler characteristic \(E \geq 0\). Then \[\chi(G) \le H(E) := floor(\frac{7+\sqrt{(49-24E)}}{2})\]
A: Let G be drawn on surface, with \(\chi(G) = k\). Claim \(k \leq H(E)\). Choose G minimal(with least n) s.t. \(\chi(G) = k\). By minimality \(\delta(G) \ge k-1\) and \(n \ge k\).
We know \(m \le 3(n-E)\) so \(2m \le 6(n-E)\)
Average degree of vertex is \(\le 6(1-E/n)\)
Then \(k-1 \le \delta(x) \le average \; degree \le 6(1-E/n) \le 6(1-E/k) \)
Then solving this quadratic gives the result

Q: Definition. Ramsey number. For \(s \in \mathbb{N}\), let \(R(s)\) be [...]
A: the smallest number n (if it exists) such that, if the edges of \(K_n\) are coloured red/blue, we always get a monochromatic \(K_s\).

Q: Definition. For \(s,t \geq 2\), define \(R(s,t)\) to be [...]
A: the smallest n, if it exists, such that if the edges of \(K_n\) are 2-coloured, there must be a red \(K_s\) or blue \(K_t\)

Q: Theorem. Ramsey's. \(R(s,t)\) exists \(\forall s,t \geq 2\). Moreover, \(R(s,t) \le R(s-1,t) + R(s,t-1) \; \forall s,t \geq 3\)
A: It is enough to show that if \(R(s-1,t)\) and \(R(s,t-1)\) are finite, then \(R(s,t) \le R(s-1,t) + R(s, t-1)\) are finite
Set \(a = R(s-1,t), b=R(s,t-1)\). Choose a 2-colouring of \(K_{a+b}\) and let x be a vertex of this graph.
Note \(d(x) = a+b-1\), so \(\exists\) one of the below from x
i) \(\geq a\) red edges
ii) \(\geq b\) blue edges
Case i) let \(N_r = \) red neighbours of x so \(|N_r| \ge a\). The colouring induced on \(N_r\) contains either a \(K_{s-1}\) in red or a \(K_t\) in blue
If the latter case we are done. In former case just add x to \(K_{s-1}\) to finish.
Case ii) is similar.

Q: Corollary. Let \(s,t \geq 2\). Then \[R(s,t) \le {s+t-2 \choose s-1}\]Taking \(R(t) = R(t,t), R(t) \le {2t-2 \choose t-1} \le 2^{2t}\)
A: Induct on \(s+t\). If \(s=2\) or \(t = 2\): \(R(s,2) = s\), \(R(2,t) =t\)
Given \(s,t \geq 3\) assume \(R(s-1,t), R(s,t-1)\) exist and satisfy our inequality, then \[R(s,t) \le R(s-1,t) + R(s,t-1) \le {s+t - 3 \choose s-2} + {s+t - 3 \choose s-1} = {s+t-2 \choose s-1}\]

Q: Corollary. \(R_k(s_1 , \dots , s_k) \) exists \(\forall k \geq 2\), \(s_1 , \dots , s_k \geq 2\)
A: Induction on k( number of colours), where the case \(k=2\) comes from Ramsey's theorem.
Suppose \(k>2\) and \(s_1 , \dots , s_k\) given, let \(n = R(s_1 , R_{k-1}(s_2 , \dots , s_k))\)
Then any k-colouring of \(K_n\) may be viewed as a 2-colouring with colours 1 and "2 or 3 or 4 or ... or k". <-- "colour blindness"
By choice of n, we have either \(K_{s_1}\) is coloured 1 (done) or a \(K_{R_{k-1}(s_2 , \dots , s_k)}\) coloured with colours \(2,3,\dots, k\) (i.e. k-1 coloured). Hence we are done by the definition of the Ramsey number.

Q: Definition. X a set, \(r = 1,2,3,\dots\)\[X^{(r)} =[...]\]As usual \(X = [n] = \{1,2,\dots, n\}\) as before
Write \(R^{(r)}(s,t)\) for [...]
A: \{A \subseteq X : |A| =r\}; the smallest n, if it exists, s.t. whenever \(X^{(r)}\) is 2-coloured(i.e. \(\exists c : X^{(r)} \to \{1(red), 2(blue)\}\)), then \(\exists\) a red s-set (an s-set all of whose r-sets are red) or a blue t-set, true for each \(r \geq 1, s,t \geq r\).
Back Extra: 1) \(R^{(2)}(s,t) = R(s,t)\)
2) \(R^{(1)}(s,t) = s+t -1 = (s-1) + (t-1) + 1\)
3) \(R^{(r)}(s,t) = R^{(r)}(t,s)\)
4) \(R^{(r)}(s,r) = s\)

Q: Theorem. Ramsey for r-sets. \(R^{(r)}(s,t)\) exists \(\forall r \ge 1, s,t \ge r\).
A: We show that, if \(a = R^{(r)}(s-1,t), b = R^{(r)}(s,t-1) \) and \(n = R^{(r-1)}(a,b) + 1\) exist, then \(R^{(r)}(s,t) \le n\)
Given 2-colouring c of \(X^{(r)} = [n]^{(r)}\), pick \(x \in X\) and \(Y = X \setminus \{x\}\). Then c induces 2-colouring c' of \(Y^{(r=1)}\) by \(c'(A) = c(A \cup \{x\}) \;\; \forall A \in Y^{(r-1)}\)
By definition of \(n-1 = R^{(r-1)}(a,b)\) exists either red a-set for c' or a blue b-set for c'.
If red a-set: \(\exists Z \le Y, |Z| = a\) s.t. \(\forall A \in Z^{(r-1)}\) we have \(c(A \cup \{x\})\) is red.
Inside \(Z\), by definition of a \(\exists\) red (s-1)-set for c or a blue t-set for c.
But a blue t-set for c means we are done; and a red (s-1)-set for c forms, together with x, a red s-set for c.
If blue b-set, same argument by swapping colours.

Q: Theorem. Infinite Ramsey's. Whenever \(\mathbb{N}^2\) is 2-coloured \(\exists\) an infinite monochromatic subset \(M \subseteq \mathbb{N}\)
A: Pick arbitrary \(x_1 \in \mathbb{N}\). By PHP \(\exists\) infinite set \(A_1 \subseteq \mathbb{N} \setminus \{x_1\}\) s.t. all the \(x_1 -A_1\) edges are of the same colour \(c_1.\)
Now pick \(x_2 \in A_1\), again we find some infinite \(A_2 \subseteq A_1\) s.t. all \(x_2 - A_2\) edges are the same colour \(c_2\)
Proceed and obtain \(x_1 , \dots\) and sequence of colours \(c_1 , \dots \) such that \(x_i x_j\) has colour \(c_i(i < j)\)
By PHP since there are finitely many colours there is an infinite subsequence that is constant, \(c_{i_1}, c_{i_2}, \dots\)
Then \(M = \{x_{i_1}, x_{i_2}, \dots\}\) is infinite monochromatic.

Q: Theorem. Infinite Ramsey for r-sets. Given \(r = 1,2,3,\dots\) whenever \(\mathbb{N}^{(r)}\) is 2-coloured there exists an infinite monochromatic subset \(M \subseteq \mathbb{N}\)
A: Induction on r.
r=1 is PHP
Let \(r > 1\) and given \(r-\)colouring c of \(\mathbb{N}^{(r)}\), fix \(x_1 \in \mathbb{N}\). We induce a 2-colouring \(c_1\) of \((\mathbb{N} \setminus \{x_1\})^{(r-1)}\) by \(c_1(A) = c(A \cup \{x\})\) for each A.
By induction \(\exists \) infinite \(A \subseteq \mathbb{N} \setminus \{x\}\) monochromatic for \(c_1\), i.e. each \((r-1)\)-set \(A_1 \subseteq A\) is such that \(A_1 \cup \{x_1\}\) gets colour \(c_1\).
Now choose \(x_2 \in A_2\) and continue as above.
This provides distinct \(x_1 , x_2 , \dots\) and colours \(c_1 , c_2 \dots\) such that the colour of the r-set \(x_{i_1}, \dots x_{i_r}\) is \(c_{i_1}\)
But infinitely many \(c_{i_1} = c_{i_2} = \dots\) agree and \(M=\{x_{i_1}, x_{i_2}, \dots\}\) is monochromatic.

Q: Theorem. Erdös. \[R(s) \ge 2^{s/2}\]
A: Choose a colouring of \(K_n\) at random - by taking each edge to be red or blue with probability 1/2 each (independently). Then \[\mathbb{P}(\text{ a fixed s-set is monochromatic}) = 2(1/2)^{{s \choose 2}}\]\[\# s-sets = {n \choose s}\]\(\mathbb{P}(\exists \text{ monochromatic s-set}) \le 2{n \choose s}(1/2)^{{s \choose 2}} = {n \choose s}2^{1 - {s \choose 2}}\)
So must have \(R(s)\) > n if \({n \choose s}2^{1 - {s \choose 2}} < 1\) i.e. if \({n \choose s} < 2^{{s \choose 2} - 1}\)
But \({n \choose s} \le \frac{n^s}{s!}\) and \(s! \ge 2^{s/2 + 1} \)(can prove by induction on for \(s \ge 3\))
So \({n \choose s} \le \frac{n^s}{2^{s/2 + 1}}\). So \(R(s) > n\) if \(n^s < 2^{s^2 / 2}\) i.e \(n < 2^{s/2}\)

Q: Definition. For \(0 < p < 1\), the probability space \(\mathcal{G}(n , p)\) is defined as follows: [...]
A: we form a graph on n vertices by selecting each edge independently, with probability p (so an edge is absent with probability 1-p)

Q: Theorem. \[Z(n,t) \ge \frac{1}{2}n^{2-\frac{2}{1+t}}\]
A: Let G be a random bipartite graph with vertex classes X,Y(|X|=|Y|=n) and edges chosen independently with probability p.
Consider random variables \[M = e(G)\]\[R = \# K_{t,t} \text{'s in G}\]We have \(\mathbb{E}[M] = pn^2, \mathbb{E}[R] = {n \choose t}^2 p ^{t^2} \le \frac{1}{2}n^{2t}p^{t^2}\)
So we have \(\mathbb{E}[M-R] \ge pn^2 -\frac{1}{2}n^{2t}p^{t^2}\)
Taking \(p = n^{-\frac{2}{t+1}}, \mathbb{E}[M-R] \ge n^{2-\frac{2}{t+1}} - \frac{1}{2}n^{2t - \frac{2t^2}{t+1}} = \frac{1}{2}n^{2 - \frac{2}{t+1}}\)
Hence there exista a graph G with m edges and r \(K_{t,t}\)'s with \(m-r \ge \frac{1}2{n^{2 - \frac{2}{t+1}}}\) and therefore \[Z(n,t) \ge \frac{1}{2}n^{2 - \frac{2}{t+1}}\]

Q: Definition. The girth of a graph G is [...]
A: the length of the shortest cycle in G.

Q: Theorem. \(\forall k,g \in \mathbb{N}\), \(\exists \) graph G with \(\text{girth}(G) \ge g\) and \(\chi(G) \ge k\).
A: For large n choose G, a random graph where \(p = n^{\frac{1}{g} - 1}\)
Let \(X_i = \# \text{i -cycles in G}\) and let \(X = \# \text{cycles of length < g}\)
So \(X_i = \sum_{x_1 \dots x_i \in [n]} I(x_1 \dots x_i \text{ is a cycle in G}) \)
So \(\mathbb{E}[X_i] = \sum \mathbb{P}(x_1 \dots x_i \text{ are a cycle in G}) = (\# \text{possible i-cycle} ) \cdot \mathbb{P}(\text{given i-cycle is present}) = {n\choose i} \frac{i!}{2i}p^i \le n^i p^i = (np)^i = n^{i/g} \le n^{(g-1)/g}\)
\(\mathbb{E}[X] = \sum_{i=3}^{g-1}\mathbb{E}[X_i] \le \sum_{i=3}^{g-1}(np)^i \le gn^{(g-1)/g} < n/4\) if n is sufficiently large
Markov's inequality \(\mathbb{P}(X > n/2) < \frac{\mathbb{E}X}{n/2} = 1/2\)
Take \(t = n/2k\) where n is a multiple of 2k
Write \(Y_t=\# \text{ t - sets that are independent}\)
\(\mathbb{E}[Y_t] = {n \choose t}(1-p)^{{t \choose 2}} \le n^t e^{-p{t\choose 2}} \le n^t e^{-p \frac{n^2}{9t^2}}\)( uses \((1-x) \le e^{-x}\) and \({t \choose 2} = \frac{n^2}{8k^2} + O(n) > \frac{n^2}{9k^2}\))
\( = \exp (\frac{n}{2k} \log n - \frac{n^2}{9k^2} n^{1/q - 1}) \to 0\) as \(n \to \infty\)
\(\mathbb{E}Y_t < 1/2\) for large n therefore \(\mathbb{P}(Y_t > 1) < 1/2\) as n gets large
Conclude that \(\exists G \in \mathcal{G}(n,p)\) with \(\le n/2\) short cycles and no independent set of size \(n /2k\)

Q: Theorem. Given constant \(\lambda\), let \(G \in \mathcal{G}(n,p)\) where \(p = \lambda \frac{\log n}{n}\)
Then if \(\lambda < 1\) then almost surely \(G\) has an isolated vertex
Then if \(\lambda > 1\) then almost surely G has no isolated vertex
So (6.6) says \( p = \frac{\log n}{n}\) is a threshold value for the property of "having an isolated vertex"
A: Let \(X = \# \text{ isolated vertices of G}\). (\(X = \sum_v I(v)\), \(I(v)\) is indicator of v being isolated)
Then \(\mu = \mathbb{E}[X] = n(1-p)^{n-1} = \frac{n}{1-p} (1-p)^n\)
For \(\lambda > 1\), \(\mu \le \frac{n}{1-p}e^{-pn} = \frac{n}{1-p} e^{- \lambda \log n} = \frac{n^{1- \lambda}}{1-p} \to 0\) as \(n \to \infty\)
Therefore \(\mathbb{P} (X = 0) \to 1\) therefore \(X = 0\) almost surely
For \(\lambda < 1\), \(1-p \ge e^{-(1+\epsilon)p}\) for any \(\epsilon >0\) and p small enough(uses \(1- x \ge e^{-(1+ \epsilon)x}\), x small)
So \(\mu \ge \frac{n}{1-p} e^{-(1+ \epsilon) pn} = \frac{n}{1-p} e^{-(1+\epsilon) \lambda \log n} = \frac{n^{1 - (1+\epsilon)\lambda}}{1-p}\)
Choose \(\epsilon > 0\) s.t. \((1+\epsilon)\lambda < 1\), then \(\mu \ge \frac{n^{positive}}{1-p} \to \infty\)
Now, \(V(X) = \sum_{u,v} \mathbb{P}(\text{u isolated})(\mathbb{P}(\text{v isolated | u isolated}) - \mathbb{P}(\text{v isolated})) = n(1-p)^{n-1}(1-(1-p)^{n-1}) + n(n-1) (1-p)^{n-1}((1-p)^{n-2} - (1-p)^{n-1})\)
split into n terms where \(u=v\) and \(n(n-1) \) terms where \(u \neq v\)
\[\le \mu + n(n-1)(1-p)^{n-1}p(1-p)^{n-2} \le \mu + n^2(1-p)^{n-1}p(1-p)^{n-2} = \mu + \frac{p}{1-p} \mu^2\]Thus \(\frac{V}{\mu^2} \le \frac{1}{\mu} + \frac{p}{1-p} \to 0\) as \(n \to \infty\)
Therefore \(\mathbb{P}(X = 0) \to 0\) as \(n \to \infty\) therefore \(X \neq 0\) almost surely

Q: Proposition. Let \(0<p<1\) be fixed, and let d be real with \({n \choose d}p^{{d \choose 2}} = 1\). Then \(G \in \mathcal{G}(n,p)\) has clique number \(\lceil d \rceil, \lfloor d \rfloor\) or \(\lfloor d \rfloor -1\) almost surely
A: Fix k and let \(X = \# K_k's\) in G. Note \(\mu = \mathbb{E}X = {n \choose k}p^{{k \choose 2}}\)
IdeaL if \(k \ge d+1\) then X = 0 a.s. and if \(k < d-1\) then \(X \ge 1\) a.s.

Q: Definition. The Moore graph is [...]
A: a k-regular graph of diameter 2 on \(n=1+k^2\) vertices.
Back Extra: Equivalently, k-regular graph is a Moore graph iff \(\forall x \neq y\) \(\exists\) unique path of length \(\le 2\) from x to y.
Equivalently, diameter is 2 and no \(C_3\) or \(C_4\) in G

Q: Definition. \(G = (V,E)\) is a graph on \(V = [n] = \{1,2, \dots , n\}\). Then the adjacency matrix of G is the \(n \times n\) matrix \(A = [a_{ij}]_{n \times n}\) where \[[...]\]
A: A_{ij} = \begin{cases} 1 & ij\in E \\ 0 & ij \not \in E\end{cases}

Q: Proposition. Let \(G = (V,E)\) be a graph with adjacency matrix A. Then
(i) If \(\lambda\) is an eigenvalue of G then \(|\lambda| \le \Delta\)
(ii) If G is connected, \(\Delta\) is eigenvalue \(\iff\)G is regular. In this case \(\Delta\) has multiplicity 1 and eigenvector \((1,1,\dots , 1)\)
(iii) If G is connected, \(- \Delta\) is eigenvalue \(\iff\) G is regular and bipartite. In this case \(-\Delta\) has multiplicity 1
(iv) \(\lambda_{\text{max}} \ge \delta\)
A: Let A be adjacency matrix.
(i) Choose eigenvector \(x = (x_1 ,\dots , x_n) \ne 0\) with eigenvalue \(\lambda\). Let i be such that \(|x_i|\) is maximal. WLOG \(x_i = 1\) and \(\forall j \; |x_j| \le 1\). Then
\[|\lambda| = |\lambda x_i| = |(Ax)_i| = |\sum_{j=1}^n A_{ij}x_j| = |\sum_{j \in \Gamma(i)} x_j| \le \sum_{j \in \Gamma(i)} |x_j| \le d(i) \le \Delta \](ii) (\(\impliedby\)) If G is \(\Delta\)-regular then clearly \(x = (1,1,\dots, 1)\) is eigenvector with eigenvalue \(\Delta\).
(\(\implies\)) If \(\Delta\) is eigenvalue, taking \(\lambda = \Delta\) in (i) \[\Delta = (Ax)_i = \sum_{j\in \Gamma(i)} x_j\]Hence \(d(i) = \Delta\) and \(\forall j \in \Gamma(i), x_j = 1\). Repeat: \(\forall j \in \Gamma(i)\) we have \(d(j) = \Delta\) and \(\forall k \in \Gamma(j), x_k = 1\). Continuing, as G connected, \(d(k) = \Delta\) and \(x_k = 1\)
(iii) (\(\impliedby\))Take \(x = 1\) on \(X\), \(-1\) on \(Y\). Then \(Ax = -\Delta x\)
(\(\implies\)) If \(-\Delta\) is eigenvalue, then \(\sum_{j \in \Gamma(i)} x_j = -\Delta\), so \(d(i) = \Delta\) and \(x_j = -1\) \(\forall j \in \Gamma(i)\).
Repeat: \(\forall j \in \Gamma(i), d(j) = \Delta\) and \(x_k = 1 \; \;\forall k \in \Gamma(j)\). Thus G is \(\Delta - regular, x_k = \pm 1 \; \; \forall k\) and \(x_k x_j = -1\)\(\forall kj \in E(G)\)(as G is connected). Evidently G is bipartite as we can partition G according as whether \(x_k = \pm 1\).
(iv) By (7.4), we have to find x, \(||x|| = 1\) and \(\langle Ax, x\rangle \ge \delta\). Take \(x = (1,1,\dots , 1)\). Then \((Ax)_i \ge \delta \; \; \forall i\) so \(\langle Ax , x \rangle \ge \delta \langle x, x \rangle = \delta n\) therefore \(\lambda_{\text{max}} \ge \delta\)

Q: Proposition. For any graph G, we have \(\chi(G) \le \lambda_{\text{max}} + 1\)
A: WLOG \(| G| \ge 2\). Choose \(v \in [n] = V(G)\) and \(d(v) = \delta\).
Put \(G' = G - v\). If we can show \(\lambda_{\text{max}}(G') \le \lambda_{\text{max}}(G)\) then we're done.
This is because we can colour G' in \(\lambda_{\max} + 1\) colours using induction and now \(d(v) = \delta \le \lambda_{max}\) so can colour v as well.
Let B be the adajacency matrix of G'. It is formed from A by deleting the v'th row and column.
WLOG this is the last (nth) row and column, we need to show \[\max_{x \in \mathbb{R}^{n-1}, ||x||= 1} \langle Bx, x \rangle \le \max_{x \in \mathbb{R}^{n-1}, ||x||= 1} \langle Ax, x \rangle\]If \(x = (x_1 , \dots , x_{n-1}) \in \mathbb{R}^{n-1}\), then \(y = (x_1, \dots , x_{n-1}, 0) \in \mathbb{R}^n\), with \(||y|| = ||x|| \) and \(\langle Bx, x \rangle = \langle Ay,y \rangle\)

Q: Definition. We say that a graph G is strongly regular with parameters \((k,a,b)\) if [...]
A: G is k-regular and any two adjacent vertices have \(a\) common neighbours and any two non-adjacent vertices having \(b\) common neighbours.
Back Extra: \(C_4\) has \((2,0,2)\)
Petersen graph has \((3,0,1)\)
\(C_5\) has \((2,0,1)\)

Q: Theorem. Let G be a strongly regular graph on n vertices with parameters \((k,a,b)\)(Assume G not complete, \(b \ge 1\)) Then the numbers \[\frac{1}{2}\left (n-1 \pm \frac{(n-1)(a-b) + 2k}{\sqrt{(b-a)^2 - 4(b-k)}} \right ) \]are integers.
A: Let A be the adjacency matrix of and let \(|G| = n\)
Evidently G is connected. By (7.5) as G is k-regular, k is eigenvalue of multiplicity 1, eigenvector \((1,1,\dots, 1)\)
What about the other eigenvalues?
Let \(\lambda \ne k\) be an eigenvalue with eigenvector \(x.\)
Recall \((A^2)_{ij} = \# \text{walks of length 2 from i to j}\), so \[(A^2)_{ij} = \begin{cases}k & i=j \\ a &ij \in E(G) \\ b & ij \not \in E(G) \end{cases}\]Thus \(A^2 = kI + aA + b(J-I-A)\) where J is all 1's matrix
\(A^2 + (b-a)A + (b-k)I = bJ\)
Apply to x, noting \(\langle x,v \rangle = 0\) so \(Jx = 0\). Hence \[\lambda^2 x = kx + a\lambda x - bx - b\lambda x \implies \lambda^2 + (b-a)\lambda + (b-k) = 0\]The remaining eigenvalues \((\ne k)\) are \(\lambda, \mu = \frac{(a-b) \pm \sqrt{(b-a)^2 - 4(b-k)}}{2}\)
with multiplicites r,s say (respecitvely)
A diagonisable, so \(r+ s+1=n\) and \(\text{tr}(A) = 0\) so \(\lambda r + \mu s + k = 0\)
\[(\lambda - \mu)s = \lambda(n-1) + k\]So \[s,r = \frac{1}{2}((n-1)\pm\frac{(a-b)(n-1) + 2k}{\sqrt{(b-a)^2 - 4(b-k)}})\]

Q: Corollary. G Moore graph of degree k. Then \(k \in \{2,3,7,57\}\)
A: We know \(a=0,b=1, n = k^2 + 1\) so we have \[\frac{1}{2}(k^2 \pm \frac{2k -k^2}{\sqrt{4k-3}}) \in \mathbb{Z}\]Two possibilities: \[2k - k^2 = 0 \implies k = 2\]\[4k-3 = t^2, t|(2k- k^2)\]Now \(k = \frac{t^2 + 3}{4}\) and \(k^2 - 2k = tr\) for some integer r. Hence \[(\frac{t^2 + 3}{4})^2 -2 (\frac{t^2 + 3}{4}) = tr\implies t^4 -2t^2 - 16tr- 15=0\]\(t | 15\) so \(t = 1,3,5,15 \implies k = 1,3,7,57\)

Q: What is Hall's Theorem?
A: Let G be a bipartite graph with vertex classes X,Y. Then G has a matching from X to Y if and only if \[|\Gamma(A)| \ge |A|\]\[\forall A \subseteq X\]

Q: What is Menger's Theorem?
A: Let G be a graph, and a,b nonadjacent vertices of G. If all a-b seperators have size \(\ge k\) then tehre exists a family of k independent a-b paths

Q: What is Brook's Theorem?
A: If G is a connected graph, not a complete graph or odd cycle then \[\chi(G) \le \Delta\]

Q: What is Vizing's theorem?
A: \[\Delta \le \chi'(G) \le \Delta + 1\]

Q: Proposition. Let G be a connected graph for which \(\delta(G) < \Delta(G)\). Then \(\chi(G) \le \Delta(G)\)
A: We find a better ordering to apply the greedy colouring to. First define \(v_n = v\) where \(d(v) \le \Delta(G) - 1\). Now choose an ordering of \(v_1 , \dots , v_{n-1}\) so that \[d(v_1, v) \ge d(v_2, v) \ge \dots \ge d(v_{n-1},v)\]We claim that each vertex \(v_i\) with \(i \in [n-1]\) has at most \(\Delta(G) - 1\) neighbours in \(v_1 , \dots , v_{i-1}\). This is true for \(v_n\) by definition. For \(v_i, i \neq n\) we observe that a shortest path P from \(v_i \) to \(v_n\) contains a neighbour \(v_j\) of \(v_i\) with \(d(v_j, v) < d(v_i , v)\), Thus \(v_j\) comes later in the ordering(that is j < i).
So the greedy colouring gives each vertex one of \(\Delta(G)\) colours.