Consider the graph G0 with 3 components which are triangles.


the number of colored edges is clearly equal to twice the number of non- monochromatic triangles.

If Ajal says blue exactly once then clearly there will be at least one monochromatic triangle.

On the other hand, Rekha can guarantee that no more than one non-monochromatic triangle is formed, to do this she makes sure she never colors a vertex with a color, if that color is already present in a triangle that hasn't been completely colored.

So there will be $2$ colored edges if the game is played optimally by both parties.


Related videos on Youtube

Author by


Updated on August 15, 2022


  • Admin
    Admin 3 months

    Consider the graph G0 with 3 components which are triangles. G0 has 9 vertices labeled A to I and 9 edges (A, B), (B, C) … as shown below. If each vertex of G0 is assigned a red or a green color, then we say that an edge is colored if its ends have different colors. Ajai and Rekha color the vertices of G0 in the following manner. Ajai proposes a color (red or green) and Rekha chooses the vertex to apply this color. After 9 turns, all the vertices of G0 are colored and the number of colored edges is counted. Suppose Ajai would like to maximize the number of colored edges while Rekha would like to minimize the number of colored edges. Assuming optimal play from both players, how many edges will be colored? Explain your reasoning. image