Prove if a graph does not contain $K_4$ minor, then it is 3-colorable.

Question

Prove if a graph does not contain $K_4$ minor (i.e. subgraph isomorphic to a subdivision of $K_4$), then it is 3-colorable.

I have a rough idea: since a minor could be generated from the original graph, say $G$, by deleting vertices(edges) or contracting edges. Only consider the edge contraction procedure. Every time I contract an edge, without loss of generality, at a time I call it $uv$. Then $\deg(uv) \geqslant \min\{\deg(u), \deg(v)\}$ (which I am not 100% sure, as long as $u$ and $v$ do not have exactly same neighbors beside each other) . Then if so, I can do this to $G$ until there are 4 vertices left. Obviously that graph could not be $K_4$. There must exist a vertex (actually 2 I think) of degree no more than 2. That means in $G$ I could always find a vertex with degree no more than 2.

That kind of vertices I can color them at the very end since I have 3 colors to choose and at most 2 were used(restricted), leaving me at least 1 possible choice. Also the deletion of that vertex (vertices) would cause the new graph having at least a vertex of degree no more than 2. Then keep doing it. This time we won't stop until there is only one edge left. We do the coloring in the reverse order of vertex deletion. Done.

Answer 1

This is a particular case of the hadwiger conjecture. The case for which $k=4$ was in fact proved by Hadwiger in the same paper in which he published his conjecture.

The proof is simple by induction on the number of vertices, I paraphrase it from this article.

Suppose there is a graph $G$ that is not $3$-colorable and does not contain $G$ as a minor. Select such a $G$ with the minimum number of vertices. Clearly $G$ is connected and must contain a circuit. pick an edge $v_1v_2$ on the circuit and let $X\neq\varnothing$ be a minimum vertex set seperating $v1$ and $v_2$. Notice that $X$ must be an independent set, as otherwise $G$ would contain $K_4$ as a minor. Let $G-e=G_1\cup G_2$ and $G_1\cap G_2=X$, such that $G_1$ and $G_2$ are connected and $v_1\in G_1,v_2\in G_2$. Form $G_i'$ from $G$ by contracting all edges in $G_i$ so that all vertices of $G_i$ are identified with $v_i$. Clearly both $G_1$ and $G_2$ are $3$-colorable. Suppose that $G_1'$ is $3$-colored with $u_1$ green and $u_2$ blue, and $G_2'$ ; is $3$-colored with $u_1$ red and $u_2$ green. Then these colorings induce a 3-coloring of $G$ with $u_l$ red, $u_2$ blue, and all vertices of X green.