Given a planar graph such that all its vertices are of degree 4, find the minimum number of colors needed to paint the map.
I've used the Euler formula for graphs $$v-e+f=2$$ where $$v$$ is the number of vertices, $$e$$ is edges and $$f$$ is the number of faces in the plane. Because the sum of all vertices' degrees of a graph equals to $$2e$$, I get $$4v=2e\Rightarrow f=2+v$$
I can't attach pics, but for 1 to 3 vertices it clearly only takes 3 colors. My question is, how to prove that it's true for arbitrary number of vertices, if it is?
I am assuming that the question asks for a colouring of the faces. In this case, the map can be coloured with only two colours. It is a bit like a checkerboard. This is actually true for any graph where all the vertices are of even degree (not necessarily all the same).
I don't know the best way to prove this, but you could do it by induction on the number of edges. Given a graph with even degree vertices, select any loop of edges from that graph. If you were to remove that loop, the vertices involved reduce their degree by 2, so remain of even degree. You are left with a graph with fewer edges, which still has all vertices of even degree. By the induction hypothesis its faces can be 2-coloured. You can now add the loop back in, and flip the colours of the area inside the loop to get a 2-colouring of the original map. As the base case(s) for the induction you can take the graphs with no edges, and any number of vertices of degree 0.