<p>Yes, Max-Cut is still NP-complete in unweighted graphs.  </p>

<p>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: </p>

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

CC BY-SA 3.0
2016-12-27T11:33:22.107Z
2016-12-27T11:33:22.107Z
Gamow
<p>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.</p>

CC BY-SA 3.0
2016-12-27T11:18:01.490Z
If you are stuck with your homework then you should rather ask your teacher for a hint.
Gamow
CC BY-SA 3.0
2016-12-27T11:25:56.590Z
I am not a student. I am a teacher and this wasn't a HW question. Well at least not one I assigned.
Burak Yıldıran Stodolsky
CC BY-SA 3.0
2016-12-30T23:28:54.470Z
This is clearly not a research level question.
ivmihajlin
<np-complete><max-cut>
Is the max cut problem still NP-Complete for graphs with unit weights on the edges?
Burak Yıldıran Stodolsky
# Is the max cut problem still NP-Complete for graphs with unit weights on the edges?

(Asked by: username_0 on 2016-12-27)

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.

**Tags:** np-complete, max-cut
> **Comments:**
> **username_1**: If you are stuck with your homework then you should rather ask your teacher for a hint.  
> **username_0**: I am not a student. I am a teacher and this wasn't a HW question. Well at least not one I assigned.  
> **username_2**: This is clearly not a research level question.  

---

## 1 answers

### Answer by username_1 on 2016-12-27. Score: 5

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


---

