I was given today in the text the following information:
G is a maximal planar graph over $n>2$ vertices.
given that $\chi(G)=3$, prove there is an Euler Cycle in the graph.
Now, I believe this isn't correct for $n>3$.
Because for every Vertex you add to the graph, you add exactly three edges. So the graph must have one vertex with an odd degree therefore there wont be an Euler cycle.
I need help in telling if im correct or otherwise what is the proof for this statement.
Best Answer
Your argument shows that no eulerian triangulation can be obtained by adding a vertex inside a face in a preixisting triangulation and splitting that face into the 3 triangles with the new vertex.
This does not show that no eulerian triangulations exist, for an example of such a graph consider the octahedron.
The theorem is true and is in fact an if and only if, although you are only asked to prove the easy direction.
If there was a vertex of odd degree you can consider the faces around that vertex, and since it's a triangulation you get a cycle of odd length around that vertex, hence not $3$-colorable.