2013 Gauss 8 Problem 19

Serena colours the hexagons on the tiling shown. If two hexagons share a side, she colours them with different colours. What is the least number of colours that she can use to colour all of the hexagons?

\textbf{(A)}\ 4\quad \textbf{(B)}\ 6\quad \textbf{(C)}\ 7\quad \textbf{(D)}\ 2\quad \textbf{(E)}\ 3

If there are no answer choices shown, enter a numerical answer.

Full credit to this problem is given to the CEMC, you may view all Gauss contests here.