In this paper, we present an exact algorithm that solves MAX-CUT in time poly(|E|) · 2^|E|/4, where |E| is the number of edges (multiple edges between two vertices are allowed). This bound improves the previously known bound poly(|E|) · 2^|E|/3 of Gramm et al. (2000). Bibliography: 8 titles.