In this question, $G$ is a graph, $E(G)$ is the set of edges of $G$, $\chi(G)$ is the chromatic number of $G$, $K_n$ is the complete graph on $n$ vertices.
Statement A:
$|E(G)| \geq {\chi(G) \choose 2}$.
Statement B:
Every graph $G$ contains a subgraph isomorphic to $K_{\chi(G)}$.
Statement C:
Every graph $G$ contains a subgraph isomorphic to a subdivision of $K_{\chi(G)}$.
Obviously, B implies C, which implies A. I have already proved that A is true, without using B or C, but these implications would give nicer proofs in my opinion.
I also see that B is false if $G$ has chromatic number 3 or 4; counterexamples are the cycle graph $C_{2n+1}$ (http://mathworld.wolfram.com/CycleGraph.html) and the wheel graph $W_{2n+1}$ (http://mathworld.wolfram.com/WheelGraph.html).
In the next questions we can exclude these small cases.
My questions are:
(1) Does C imply B? That is, are they actually equivalent?
(2) Is C true?
(3) Is B true?
Best Answer
Statement B is false: for any positive integer $n$ there is a graph $G$ which is triangle-free (contains no subgraph isomorphic to $K_3$) and has chromatic number $\chi(G)\gt n.$
Proof. Let $G=(V,E)$ where $$V=\{(x,y):0\le x\lt y\le2^n\},$$ $$E=\{\{(x,y),(y,z)\}:0\le x\lt y\lt z\le2^m\}.$$ Clearly $G$ is triangle-free. To see that $\chi(G)\gt n$ consider any coloring $f:V\to[n]=\{1,2,\dots,n\}.$ Define a function $\varphi:\{0,1,\dots,2^n\}\to\mathcal P([n])$ by setting $\varphi(x)=\{f(x,y):x\lt y\le2^n\}.$ Choose $x,y\in\{0,1,\dots,2^n\}$ with $x\lt y$ and $\varphi(x)=\varphi(y).$ Since $f(x,y)\in\varphi(x)=\varphi(y),$ we can find $z$ such that $y\lt z\le2^n$ and $f(y,z)=f(x,y),$ i.e., $f$ is not a proper coloring of $G.$ This shows that $\chi(G)\gt n$; in fact, it is easy to see that $\chi(G)=n+1.$
Update. Statement C is the Hajós conjecture. The statement "every graph of chromatic number $n$ contains a subgraph isomorphic to a subdivision of $K_n$" is known to be true for $n\le4$ and false for $n\ge7;$ the cases $n=5$ and $n=6$ seem to be unsolved problems. The statement for $n=5,$ that every graph of chromatic number $5$ contains a subgraph isomorphic to a subdivision of $K_5,$ would be a strengthening of the four color theorem.