I am referring to Computational Complexity by Arora and Barak for my course. In the section on NP-completeness reductions, the book has a diagram that is represents how one NP-complete
problem language can be reduced to other problem(s) language(s). This is the picture from the book:
However, even after thinking for quite some time, I can't think of a reduction from Vertex Cover to Max-Cut. Nor could I find any resource online. My question is, is there any (non-trivial*) reduction? Or is it some kind of misprint?
*Non-trivial meaning that it's not of the forms: 1) Vertex Cover -> SAT -> ... -> Max-Cut using Cook-Levin Theorem, or 2) Vertex Cover -> L -> ... -> Max-Cut, where L is some really unrelated language to both VC and Max-Cut.
Note: Even though the arrow reads Ex 2.16, the actual Ex 2.16 just asks to prove that Max-Cut is NP-complete. Also, this is not a homework question.