I want to show the following:
If a graph $G$ has $O(|V|)$ edges, then we can color $G$ with $O(\sqrt{|V|})$ colors.
I tried to use induction on number of nodes and number of edges, but neither could lead to the conclusion.
Here's an definition of vertex coloring.