Collection of Maths Problems

Quadrangular faces

Task number: 4098

• Hint

  The graph can have an odd cycle as a subgraph, but not necessarily as a face.

• Solution

  For example, the toroidal grid $3 \times 3$ contains a triangle, and it can be colored with three colors, see the picture.

  

• Variant

  Try to find a graph with the same drawing conditions, but to have the chromatic number four.

• Hint

  Try to start with the grid again, but this time wind it on the torus in a skewed way.

  Algebraic tools, namely Cayley graphs , can be used to describe such a graph. Cayley graph for the group $G$ and the set of generators $X \subseteq G$ is a graph on $| G |$ vertices $V$, where each vertex corresponds to one element of the group $G$ and the edges correspond to the composition with generators.

  In other words, there is a bijection $f: V \rightarrow G$ such that the vertices of $u, v$ are joined by an edge, iff there is $x \in X$ that $f (u) x = f (v)$ or $f (u) x^{-1} = f (v)$. The Cayley graph is usually denoted as $Cay (G, X)$.

  Examples: $C_5 = Cay (\mathbb Z_5, \{1 \})$, $K_5 = Cay (\mathbb Z_5, \{1{,}2 \})$.

• Solution

  Take the Cayley graph $G = Cay (\mathbb Z_{13}, \{1{,}5 \})$. This graph can be drawn on a torus with quadrangular faces.

  

  It contains an odd cycle of 0-12, so its chromatic number is at least 3.

  We show by a contradiction that the chromatic number is at least 4. If $G$ could be colored with three colors, one of the colors would have to be used at least five times. Without loss of generality, let it be red and let 0 be red. Red cannot be used on its neighbors, so four of the remaining eight vertices must be red. On these vertices we can find an eight-cycle 2-3-4-9-10-11-6-7, so either red are 2,4,10 and 6; or 3,9,11 and 7. The first option is excluded due to the edge $(2{,}10)$ the second due to $(3{,}11)$.

  

  However, coloring with four colors exists, indeed one of the colors needs to be used only once.

  

• Variant

  Can you find a graph that has a chromatic number four and whose drawing in the projective plane would have all the faces quadrangular?

• Solution

  Just cleverly draw the graph $K_4$. It has three faces, they are marked in color in the picture.