A plane graph with $n\ge 3$ vertices has at most $3n-6$ edges, which is achieved by plane triangulation
Planar Graph: If it can be embedded in the plane: if it is isomorphic to a plane graph.
Minors and Topological Minors
Definitions of Minors:
Remove vertices, then remove edges, then contract edges arbitrarily
In the exact order: remove vertices, remove edges, contract edges
$G$ contains $H$ as a minor if letting $v_1…v_h$ be the vertices of $H$, there are disjoint connected subgraphs $X_1…X_h$ such that $(v_i, v_j)\in E(H)$ means that $X_i,X_j$ in $G$.
Equivalence Proof:
1 $\Rightarrow$ 2 is trivially true
2 $\Rightarrow$ 3: Remove all vertices not in $H$, all edges not in $H$, and contract each $X_i$ to $v_i$.
3 $\Rightarrow$ 1: For any edge contraction on $(x,y)$, we ‘uncontract’ by union the vertex sets $x, y$ are in. $v_i, v_j$ edge is an $X_i, X_j$ edge because edges are never deleted, so this edge is present in $G$ too.
If $\Delta(H)\le 3$, and $H$ is a minor of $G$, then $H$ is a topological minor of $G$
Proof: Use definition 3 above. Get a tree $T_i$ on $X_i$.
Every topological minor is also a minor
Kuratowski’s and Wagner’s Theorem
Lemma 4.4.2: A graph $G$ contains $K^5$ or $K_{3,3}$ as minors if and only if it contains them as topological minors
Proof: Suffice to show that a $K^5$ minor leads to $K^5$ topological minor, or $ K{3,3} $ minor. If all trees in $ IK^5 $ are $ K{1,4} $ then we have a $K^5$ topological minor. Otherwise, there are two vertices of degree $3$, and the 6 vertices form a $K_{3,3}$ minor.
Lemma 4.4.3 Every 3-connected graph $G$ without $K^5$ or $K_{3,3}$ minor is planar
Proof: Prove by induction on $|G|$. Base case is $K^4$, true. Consider $G$ contract edge $xy$. The remaining graph is planar by induction, and 3-connected by lemma 3.2.4. If we remove vxy, it is 2-connected. So the boundary is a cycle. Denote Pi to be the path from $xi$ to $x{i+1}$. If we can show that all of $y$ neighbors are in a certain segment path Pi, then we can put $y$ in and still have a planar graph. Case 1, y has a neighbor in $P_i$ and one outside, then $y’, y’’$ are separated by two of x neighbors, there is a k3,3. Case 2, y’s neighbors are a subset of x neighbors. Thus, if y has 2 neighbors, this is case 1. If y has more than 2, then there is a TK5. Thus, it must be planar.
Crossing Numbers:
5. Coloring
Four color theorem, Kempe Chain:
Greedy Algorithm:
Can be arbitrarily good or bad. There exists a vertex ordering such that the greedy gives the best chromatic number. There exists bipartite graph can be colored with an arbitrarily large number of colors using the greedy algorithm (not connecting vi and ui).
Coloring Number $col(G)$:
The min k such that there exists an ordering, each vi has back-degree $< k$.
$col(G)\le max \delta(H) + 1$ if we use max to min ordering
$col(G)\ge col(H) \ge \delta(H) + 1$ easily
Thus, 5.2.2, $\chi(G)\le col(G) = max \delta(H)+1$
Planar graphs are 6-colorable, 5-colorable: Proof by Kempe Chain
Brook’s theorem:
If $G$ is neither complete nor an odd cycle, then $\chi(G)\le \Delta(G)$
Proof is by induction
Lower bounds and Upper bounds of $\chi(G)$:
Lower:
$\omega(G)$. Obvious.
$\frac{n}{\alpha}$. Obvious, each color has at most $\alpha$ vertices
Upper:
$\Delta(G)+1$: Greedy algorithm
$n-\alpha +1$
$\Delta(G)$ for not complete or odd cycle graphs. Brook’s Theorem.
Edge coloring $\chi’(G)$:
Konig Theorem: Every bipartite graph $G$ satisfies $\chi’(G)=\Delta(G)$.
Vizing’s Theorem:
$\Delta(G)\le \chi’(G)\le \Delta(G)+1$
List coloring $ch(G)$:
$ch(G)\ge \chi(G)$
Examples where $ch(G)>>\chi(G)$. hw7 q5. We show that there are graphs with $\chi(G)=2$ and $ch(G)=k$. We first show that there is a graph with $ch(G) \ge k$. Then we show that $ch(G-v)$ is at least $ch(G)-1$. Thus we can remove one vertex at a time to get $ch(G)=k$.
Perfect Graphs:
Perfect elimination ordering:
For all $v_i$, its neighbors that come before it form a clique.
Proof that PEO graph is perfect
put max-clique vertex the end
Chordal Graph:
PEO graphs are chordal
Weak and Strong Perfect Graphs:
cliques, bipartite, and complements
A bipartite graph’s complement is perfect
Proof: Let $G$ be bipartite, then $\chi(\bar G) = M + n - 2M = n - M$. This is because $G$ has only cliques of 1, 2. This is the minimum number of cliques in $G$. In a bipartite graph, $M = n - \alpha$.
7 Extremal Graph Theory
$R(H_1, H_2, … H_k)$ is the minimum $N$ such that every k coloring of the edges of $k^N$ yields some $i\in [k]$ for which $H_i$ is a subgraph of the ith color.
SCHUR $S(k)$ is the largest $N$ such that $[N]$ can be partitioned into k sum free sets.
Van Der Waerden is the least $N$ such that partitioning $[n]$ into R sets must yield.