Exponential time local search heuristics for Weighted MAX-CUT-Flip
Check out the paper: On the Power of Nodes of Degree Four in the
Local Max-Cut Problem - Burkhard Monien and Tobias Tscheuschner.

In the paper they take a sub-graph of size 5 constructed from two types of vertices (they call them type-1 vertices and type-3 vertices). Then they build a graph from n sub-graphs concatenated, and show a specific initial start of the max-cut algorithm. In this initial start, there would be an exponential number of flips until the local optima would be obtained.