Prove that graphs with no K4 minor are 2-degenerated.

169 Views Asked by At

Prove that graphs with no K4 minor are 2-degenerated.

I can think about a counterexample for this statement. Consider a vertex with 3 vertices adjacent to it, and these 3 vertices are not pairwise adjacent.

This graph has no K4 minor, but it is not 2-degenerated.