The problem of describing the set of all small Mahler measures of polynomials with integer coefficients is a difficult one. One approach is to look for possible candidates among polynomials attached to combinatorial objects. In this paper we study the Mahler measure of polynomials coming from non-bipartite graphs: we classify all such graphs that have Mahler measure below the golden ration. This bound is natural in that it is found to be the smallest limit point of the set of Mahler measures of connected non-bipartite graphs.