By induction on the number of edges. A tree has one face. Otherwise some edge lies on a cycle; its two sides lie in different faces, and deleting it merges them.

For a connected graph with a cycle, every face is a side face of the edges of a cycle, hence of at least $3$ edges; each edge has at most $2$ side faces, so $3f \leq 2e$, and Euler's formula $v - e + f = 2$ gives $e \leq 3v - 6$. Trees have $v - 1 \leq 3v - 6$ edges. Disconnected graphs split into a component and the rest, and the bound is superadditive.

If every vertex had degree at least $6$, the degree sum $2e$ would be at least $6v$, contradicting the edge density bound $e \leq 3v - 6$. Graphs with at most $6$ vertices are handled directly.

By induction on the number of vertices: remove a vertex of degree at most $5$, color the remaining graph, and give the removed vertex a color not used by any of its neighbors.