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 ur reasoning.

• Solution
  The optimal play is as follows.
  Rekha should choose any 2 components of G0.
  Let them be denoted as X and Y.
  If Ajai proposes red color, Rekha should apply it to any vertex of component X (always of one and
  the same component).
  If Ajai proposes green color, Rekha should apply it to any vertex of component Y (always of one
  and the same component).
  Thus, the vertices of the same component always will get the same color.
  Rekha should act in this way until all vertices of one of these initially chosen components (X or Y)
  have got some color (this color will be the same for all vertices of such component).
  Let another initially chosen component be denoted as X1.
  Let the remaining component of G0 be denoted as Y1.
  Then Rekha should operate with X1 and Y1, just as he did with X and Y, applying the same color
  to the vertices of the one component.
  That is, Rekha should apply to the vertices of X1 the same color as he had to apply to the vertices
  of X1 before. Other color should be applied to the vertices of Y1.
  Rekha should act in this way until all vertices of one of these components (X1 or Y1) have got
  some color.
  At this moment, all vertices of two components of G0 are assigned some color and the vertices
  of each component have the same color. Therefore, each of the six edges of these two
  components has the same color ends. That mean all 6 edges of these two components are not
  “colored” (to benefit Rekha). This is true regardless of in what order Ajai proposed the colors.
  After that, the color proposing for the 9-th time, Ajai should propose a color that does not
  coincide with the color of the other vertices of last component. So, some vertex of this
  component will have color different than color of other ones.
  Therefore, the last component will have 2 colored edges.
  Answer:
  Assuming optimal play from both players, 2 edges will be colored.
• 6 years agoHelpfull: Yes(1) No(0)