Print LaTeX

Hadwiger’s conjecture and Random graphs

A random graph $G(n, \frac{1}{2})$ on $n$ vertices, is obtained by starting with a set of $n$ and adding every possible edge independently with probability $\frac{1}{2}$.

Hadwiger’s conjecture states that if an undirected simple graph $G$ has no $K_{t+1}$ minor then $G$ is $t$-colorable.

Prove that almost every $G(n, \frac{1}{2})$ graph satisfies Hadwiger’s conjecture.

Source: folklore
delete flag offensive retag edit Add to a Problem Set

Related books