AMC 2010 Graph Connection Problem

Question

There are many towns on the island of Tetra, all connected by roads. Each town has three roads leading to three other different towns: one red road, one yellow road and one blue road, where no two roads meet other than at towns. If you start from any town and travel along red and yellow roads alternately (RYRY...) you will get back to your starting town after having travelled over six different roads. In fact RYRYRY will always get you back to where you started.
In the same way, going along yellow and blue roads alternately will always get you back to the starting point after travelling along six different roads (YBYBYB). On the other hand, going along red and blue roads alternately will always get you back to the starting point after travelling along four different roads (RBRB).
How many towns are there on Tetra?

---

I drew some graphs, but nothing works.

Answer 1

I'll try to rephrase your question. (Assuming I understand it correctly. Edit: I didn't.)

Let $G=(V,E)$ be planar, $3$-regular connected graph with $\chi'(G)=3$
($G$ edges could be color in $3$ colors properly. Edge coloring)
$G$ also satisfy the following property:
For every two colors, Every path of length $6$ with those two alternating colors, is a cycle.

Find $\vert V \vert$

$\require{enclose} \enclose{horizontalstrike}{\textbf{Answer}: 6}$

Proof by a drawing:

As the comments stated, I solved the wrong question, this solution does not satisfy the requirement that there are exactly two colors, such that every path with those alternating color of length 4 is a cycle.

I'm keeping this post because I hope it will help others.

Answer 2

I think you can do it with 24 islands; feel free to check if it works.

I did it in a Sudoku-like fashion though, so I would also be interested in how/whether this number could be computed from the question without explicitly drawing the graph. If my memory of AMC serves right, it was multiple choice back in the day, so maybe they were expecting ruling out some answers using the degree constraints?

Answer 3

I've seen a number of sophisticated graphical methods for solving this, but once noticing that the graph is comprised of loops of length 4, 6 and 6 - you might recognise the relationship with a truncated octahedron (an Archimedean solid). It exhibits the symmetry properties required and has degree 3 at each vertex -- still might be necessary to draw it out to verify that the colours can match up correctly, but this was my key to solving it -- and also will make it easy to verify that it is planar.

Truncated Octahedron with coloured roads

Planar representation of Tetra