We know that finding a max cut for weighted graphs is NP-Complete. I am trying to find a proof showing that even for graphs with just unit weights (every edge has weight 1) it is still NP-Complete. I've looked at the proofs reducing 3 NAESAT and vertex cover problems to max cut. But in those proofs we get weighted graphs for which we find max cuts. If someone could point me in the right direction I would appreciate it.


closed as off-topic by Mohammad Al-Turkistany, Hsien-Chih Chang 張顯之, Sasho Nikolov, Jeffε, Jan Johannsen Jan 9 '17 at 9:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Mohammad Al-Turkistany, Hsien-Chih Chang 張顯之, Sasho Nikolov, Jeffε, Jan Johannsen
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ If you are stuck with your homework then you should rather ask your teacher for a hint. $\endgroup$ – Gamow Dec 27 '16 at 11:18
  • 2
    $\begingroup$ I am not a student. I am a teacher and this wasn't a HW question. Well at least not one I assigned. $\endgroup$ – Burak Yıldıran Stodolsky Dec 27 '16 at 11:25
  • $\begingroup$ This is clearly not a research level question. $\endgroup$ – ivmihajlin Dec 30 '16 at 23:28

Yes, Max-Cut is still NP-complete in unweighted graphs.

This is explained in pretty much every survey article on tthe Max-Cut problem, and in many texbooks (as for instance "Computational Complexity" by C.H. Papadimitriou). The first proof goes back to the year 1976:

M.R. Garey, D.S. Johnson, L. Stockmeyer
Some simplified NP-complete graph problems
Theoretical Computer Science 1 (1976), pp 237-267


Not the answer you're looking for? Browse other questions tagged or ask your own question.