[Math] How to prove that if a graph $G$ has $O(|V|)$ edges, then we can color $G$ with $O(\sqrt{|V|})$ colors

Question

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.

Answer 1

Run the greedy algorithm. When color $n$ is used for the first time, to color a vertex $v$, mark the edges joining $v$ to vertices already colored (of which there will be at least $n-1$).

Every marked edge is marked only once during the process and at least $0 + 1 + \dots (c-1) = c(c-1)/2$ edges will be marked where $c$ is the number of colors used. Therefore, if $c$ colors are required there will be at least $c(c-1)/2$ edges in the graph. This bound is attained for a complete graph on $c$ vertices.