Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

Quadrangular faces

Task number: 4098

Find a graph that can be drawn on a torus so that all faces are bounded by a four-cycle and have the chromatic number three.

  • Hint

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

  • Solution

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

    Torus, chromatic number 3
  • 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 XG 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:VG such that the vertices of u,v are joined by an edge, iff there is xX that f(u)x=f(v) or f(u)x1=f(v). The Cayley graph is usually denoted as Cay(G,X).

    Examples: C5=Cay(Z5,{1}), K5=Cay(Z5,{1,2}).

  • Solution

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

    Cayley graph

    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).

    Cayley Graph Coloring

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

    Coloring with four colors
  • 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 K4. It has three faces, they are marked in color in the picture.

    K4 on the projective plane
Difficulty level: Hard task
Reasoning task
Solution require uncommon idea
Cs translation
Send comment on task by email