A puzzle about graph coloring.

Question

Let $G$ be a graph with three disjoint triangles(i.e. the graph is not connectd and has three connected components each of which is a triangle). If each vertex of G is assigned a red or a green color, then we say that an edge is colored if its ends have different colors. Person A and Person B color the vertices of G in the following manner. A proposes a color (red or green) and B chooses the vertex to apply this color. After 9 turns, all the vertices of G are colored and the number of colored edges is counted. Suppose A would like to maximize the number of colored edges while B would like to minimize the number of colored edges. Assuming optimal play from both players, how many edges will be colored?

This is a puzzle I would like to know the answer to. I suspect that finally two triangles will have the same color for all vertices while the third one will have two same and one different color.

What is the correct logic?

Answer 1

This is a rather tentative answer, as I don't have a proof that this is the best strategy on either part, but it might be useful none the less.

The first pick of course doesn't matter, so say it's red ($r$), so we have the triangles: $$ (r,\cdot,\cdot), (\cdot, \cdot, \cdot), (\cdot, \cdot, \cdot) $$ If $A$ picks $r$ again, $B$ can put it on the first triangle, which is a loss for $A$, then applying the same idea, $A$ can pick $$ (r,\cdot,\cdot), (g, \cdot, \cdot), (\cdot, \cdot, \cdot) $$

Then no matter whether $A$ picks $r$ or $g$, $B$ can place it in $B$'s favour (so say it's $r$) $$ (r,r,\cdot), (g, \cdot, \cdot), (\cdot, \cdot, \cdot) $$

$(\ast)$If $A$ keeps picking $r$, $B$ can force two monochrome triangle before colouring a vertex on the second triangle: $$ (r,r,r), (g, r, \cdot), (r,r,r) $$ Then $A$ finishes with 2 edges.

If at $(\ast)$ $A$ picks $g$, $B$ can place it on the second triangle: $$ (r,r,\cdot), (g, g, \cdot), (\cdot, \cdot, \cdot) $$ $A$ can't pick $r$ or $g$ without losing a triangle, and then choosing the other colour for the pick after would lose another triangle, so $A$'s best option is to pick one colour twice: $$ (r,r,r), (g, g, \cdot), (r, \cdot, \cdot) $$ But then we're back to a similar postion as $(\ast)$, if $A$ at any point picks $g$, then second triangle is lost to $B$, but only picking $r$ loses the third, so in either case the best $A$ can get is two edges on of the triangles (choose the same colour for the last three moves): $$ (r,r,r), (g, g, r), (r, r, r) $$

Answer 2

Your conjecture is correct. B always wins by a score of $7$ to $2$.

We first show that B will have ensured victory by the fifth move.

At the end of the game, any triangle with all one color goes to person B by a score of $3$ to $0$ and any triangle with two colors goes to A by a score of $2$ to $1$. Therefore, if B can fill any one of the triangles with one color, he wins by a score of at least $5$ to $4$.

To avoid losing within the first three moves, A must choose two of one color and one of the other. B will place the two like colors on the same triangle and the different color on another triangle. Let's say the first triangle has two green colored vertices, the second triangle one red colored vertex and the third triangle is empty. If A chooses green, B will fill in the first triangle and ensure victory. If A chooses red, triangle 1 will have two green colored vertices and triangle 2 will have two red vertices. No matter which color person A chooses, B will be able to win a complete triangle on the next move.

Continuing play, after $5$ moves triangle 1 will have all one color(green) and triangle 2 wll have two of one color(red). If A chooses green, B will place it on the third triangle. If A chooses red, B will fill in the second triangle and will have won two complete triangles. Eventually, either A chooses another red giving B triangle 2 or chooses all greens which gives B triangle 3 and A triangle 2. Therefore, B wins $7$ to $2$.

Answer 3

Assuming optimal play, there will be 4 colored edges.

First, the only possible answers are 0,2,4 or 6 colored edges. (If a triangle has both colors, it contributes two edges. Otherwise, it contributes zero edges)

Next, see that B can always completely fill up one triangle with a single color: Without loss of generality, say A gives red first. Then, B puts red in triangle 1. If A chooses green, B puts it in the other triangles. When A gives red, it goes in triangle 1. If A chooses red more than 3 times, triangle 1 gets colored completely with red. If not, triangle 2 and 3 get colored completely green.

Finally, A can always ensure that there are atleast 4 colored edges. Look at the sequence $r,r,r,g,g,g,g,g,g$. There are only three possible ways red can be distributed, and in each case you get atleast 4 colored edges.

Hence, with optimal play, there will be 4 colored edges.