Let $G$ be a finite graph. Prove that $χ(G) ≤ ∆(G) + 1$.

Symmetric proof to Wilf’s theorem.

Notice that if $H$ is a subgraph of $G$, $\Delta(H)\le \Delta(G)$ (since for any vertex $v$ in $H$, all of its edges in $H$ will be in $G$ as well).

Let $G_1=G$. Pick $v_1\in V(G_1)$ with $\deg(v_1)\le \Delta(G_1)$.

Let $G_2=G_1\backslash \{v_1\}$ (the induced subgraph when you remove $v_1$). Then pick $v_2\in V(G_2)$ with

$$ \deg_{G_2}(v_2)\le \Delta(G_2)\le \Delta(G_1) $$

Doing this iteratively, we get an enumeration $V(G)=\{v_1,\dots,v_n\}$ where

$$ \forall i\quad \deg_{G_i}(v_i)\le \Delta(G) $$

We can define a coloring inductively $c:V(G)\to \left\{0,\dots, \Delta(G)\right\}$. First, let $c(v_n)=0$.

Assume $c(v_n),\dots ,c(v_{i+1})$ have been correctly defined. Recall that $\deg_{G_i}(v_i)\le \Delta(G)$, so there are at most $\Delta(G)$ neighbord of $v_i$. So the set of colors

$$ S=\{c(w):w\in V(G_i) \text{ is a neighbor of }v_i\} $$

has at most $\Delta(G)$ elements; i.e. there is some color from $\left\{0,\dots, \Delta(G)\right\}$ that is not in $S$. So we can define $c(v_i)$ as the least such color (not appearing in $S$) and get a valid coloring on $G_i$.

Find an example of a finite graph $G$ such that $χ(G) < ∆(G) + 1$.

The cycle on 2 vertices. $\Delta(G)+1=2+1=3$, but $\chi(G)=2$.

Find an example of a finite graph $G$ such that $χ(G) = ∆(G) + 1$.

The cycle on 3 vertices. $\Delta(G)+1=2+1=3$ and $\chi(G)=3$.

Let $G$ be a finite graph, and let $V_1$ and $V_2$ be two enumerations of $V (G)$. Let $A_1$ denote the adjacency matrix of $G$ obtained from using the enumeration $V_1$, and let $A_2$ denote the adjacency matrix of $G$ obtained from using the enumeration $V_2$. Prove that $A_1$ and $A_2$ are similar.

The adjacency matrix $A_2$ can be derived from $A_1$ through a series of row & column swaps. Specifically, the same swaps must occur in both the rows and columns (as they are both indexed by the vertices).

Since similarity is transitive, it suffices to show that any $n\times n$ matrix $A$ is similar to the matrix $B$ resulting from simultaneously swapping the $i$th and $k$th rows and columns of $A$. That is,

The key observation is that $A$ is simply $B$ under a change of basis. Consider the invertible matrix $M$ whose columns are the standard basis vectors with the $i$th and $k$th vectors swapped:

$$ M=\begin{pmatrix} \vec {e_1}&\dots &\underbrace{\vec{e_i}}{k\text{th column}}&\dots& \underbrace{\vec{e_k}}{i\text{th column}}& \dots& \vec{e_n} \end{pmatrix} $$

We can show that $A=M^{-1}BM$ through matrix multiplication. (Note that $M^{-1}=M$.)

So indeed $A$ is similar to $B$.

This implies $A_1$ is similar to $A_2$.

Let $G$ be a finite graph with at least one edge, and let $A$ be its adjacency matrix. Prove that the largest eigenvalue of $A$ is positive and the smallest eigenvalue of $A$ is negative.

By Lemma 4.2.1 (Spielman),

$$ d_\text{ave}\le \mu_1 $$

Since $G$ has at least one edge, there is some vertex $v\in V(G)$ with $\deg (v)\ge 1$. And since degrees are always nonnegative, this forces $d_\text{ave}>0$. So $\mu_1$ must also be positive.

The adjacency matrix always has zeros along the diagonal (presuming no self-loops). So its trace is $0$. And the trace of a matrix is exactly the sum of its eigenvalues. Since $\mu_1>0$, this forces there to be at least one negative eigenvalue. Thus, the lowest eigenvalue of $A$ is negative.

Let $G$ be a finite graph. Prove that

$$ χ(G) ≤ \max\left\{δ(H) : H\text{ is a subgraph of }G \right\} + 1 $$

Induction on the number of vertices.

Base case: If $G$ has has a singular vertex, $\chi(G)=1$ and $\max\left\{δ(H) : H\text{ is a subgraph of }G \right\} =0$ since the only subgraph is $G$ itself. So indeed

$$ χ(G) ≤ \max\left\{δ(H) : H\text{ is a subgraph of }G \right\} + 1 $$

Inductive step: Assume this is true of all graphs with $|V(G)|\le n$. Then let $G$ be a graph on $n+1$ vertices and let $a=\max\left\{δ(H) : H\text{ is a subgraph of }G \right\}$. Consider the induced subgraph $G'=G\backslash \{v\}$ derived by removing the vertex $v$ of minimal degree. Then,

$$ χ(G') ≤ \max\left\{δ(H) : H\text{ is a subgraph of }G' \right\} + 1 ≤ a + 1 $$

(as every subgraph of $G'$ is a subgraph of $G$.)

So there exists a coloring

$$ c:V(G')\to \left\{0,\dots,a\right\} $$

This can be extended to $v$, since $v$ has exactly $\delta(G)$ neighbors, and $\delta(G)\le a$ as $G$ is a subgraph of itself.

So the number of distinct colors the neighbors of $v$ have is no more than $a$; that is, there is some color in $\left\{0,\dots,a\right\}$ which we can assign to $v$ without it conflicting with a neighbor.