Australian AMC 2012 - Middle Primary Question 9

Mary colours in a honeycomb tessellation of hexagons. If hexagons share a common edge, she paints them in different colours.

What is the smallest number of colours she needs?