Australian AMC 2012 - Upper Primary Question 7

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?