3
$\begingroup$

Problem: In a graph a 3 colouring (if one exists) has the property that no two vertices joined by an edge have the same colour, and every vertex has one of three colours, R, B, G. Consider the graph below.

Graph for this question

How can I show in any 3 colouring of this graph the opposite corners must have the same colour?

Where I am at: I can come up with several visual examples that conform to this criterion but I can not generalize across these examples.

$\endgroup$

2 Answers 2

4
$\begingroup$

Color the central vertex $(0, 0)$ in some specific color (let it be R)

Note, two opposite vertices, neighboring $(0,0)$ should have the same color, both right $(1, 0)$ and left $(-1, 0)$, and above $(0 ,1)$ with below $(0, -1)$. They share two common neighbors !

At this point you can pick one of the two colors for $(1, 1)$.

If color picked is the same as for $(0, 1)$ - go clock-wise and see, that colors are doomed (you end up with all of the corners with the same color).

Clockwise solution

Otherwise, go counter-clockwise and see colors also doomed, but now corners would have two colors.

Counter clockwise solution

$\endgroup$
0
$\begingroup$

Put red in the middle node. Then the center's four adjacent nodes are fully constrained (opposites green, other opposites blue). Now you're free to put either red or blue in the left-most. Here is red. Everything else is constrained fully:

enter image description here

Try a blue at the left-most instead and everything is constrained.

Thus there are only two solutions (up to color-interchange symmetry).

$\endgroup$

You must log in to answer this question.