How many colorings are in a complete bipartite graph which is planar and has Eurlerian path?

1.2k Views Asked by At

Let $G$ be a complete bipartite graph of $7$ vertices. $G$ is also planar and has Eulerian path. What is $G$'s chromatic number?

I think that because $G$ has Eulerian path then it must have two vertices of odd degree. Because $G$ is a complete bipartite graph then the odd degree vertices must form one partition while $5$ other vertices must form another partition (because according to complete bipartite graph definition the vertices belonging to the same partition must have the same degree, so if there were more than $2$ vertices of odd degree then the graph wouldn't have Eulerian path). So our graph is $K_{2,5}$: enter image description here

and because it's also planar it looks like this:

enter image description here

So only two colors suffice to color the graph and $\chi(G)$ cannot be less than that because there's at vertices of at least degree $2$.

I'm not sure if my proof is good especially the beginning.

1

There are 1 best solutions below

0
On BEST ANSWER

If all you're being asked to find is the chromatic number, I'd consider the following lemma whenever you have a bipartite graph:

Lemma A biparite graph with at least one edge has chromatic number 2.

Proof:

Let $\Gamma$ be a bipartite graph with at least one edge. Then the vertices of gamma can be partitioned into two sets $R$ and $B$ with no edges between vertices that are both in the same set. Now assign colors to the vertices by calling vertices in $R$ red and in $B$ blue. So $\Gamma$ has chromatic number at most $2$ and we only need to eliminate the possibility that $\Gamma$ can be $1$-colored.

$\Gamma$ would be $1$-colorable if we could pick one of the sets $R$ or $B$ to contain all the vertices. Since $\Gamma$ has an edge this is impossible so the chromatic number of $\Gamma$ is greater than $1$.