<p>Take a clique of size 5 and consider a graph on <span class="math-container">$n = 5k$</span> nodes consisting of <span class="math-container">$k$</span> copies of this clique. The size of a maximal cut in this graph is <span class="math-container">$6k = 6n/5$</span>. Indeed, from each copy we can maximally have 6 edges in a cut.</p>
<p>By the following lemma the size of a maximal cut can not be much smaller.</p>
<blockquote>
<p><strong>Lemma.</strong> In any undirected 4-regular with <span class="math-container">$n$</span> nodes there exists a cut with at least <span class="math-container">$\lceil 6n/5 \rceil$</span> edges.</p>
</blockquote>
<p>More precisely, for <span class="math-container">$n$</span> divisible by 5 the answer to your question is exactly <span class="math-container">$6n/5$</span>. For other <span class="math-container">$n$</span> it can be a bit bigger, but only by a <span class="math-container">$O(1)$</span> term. Indeed, we can again consider a graph where all but <span class="math-container">$O(1)$</span> nodes are paritioned into  copies of a 4-regular clique.</p>
<p><strong>Proof.</strong> Let <span class="math-container">$G = (V, E)$</span> be a 4-regular graph with <span class="math-container">$n$</span> nodes and let <span class="math-container">$(S, T)$</span> be a maximal cut. For a node <span class="math-container">$a\in V$</span> let cut-degree of <span class="math-container">$a$</span> be the number of edges containing <span class="math-container">$a$</span> and belonging to the cut <span class="math-container">$(S, T)$</span>. We rely on the following two easily verifiable observations:</p>
<ul>
<li><em>Observation 1: any node has cut-degree at least 2.</em> Indeed, assume that <span class="math-container">$a\in V$</span> has cut degree at most <span class="math-container">$1$</span>. WLOG, <span class="math-container">$a\in S$</span>. Then removing <span class="math-container">$a$</span> from <span class="math-container">$S$</span> and putting it to <span class="math-container">$T$</span> would result in a larger cut, contradiction.</li>
<li><em>Observation 2: no edge of the cut connects two nodes with cut-degree 2.</em> Indeed, assume that nodes <span class="math-container">$a\in S$</span> and <span class="math-container">$b\in T$</span> are adjacent and both have cut-degree 2. Then swapping <span class="math-container">$a$</span> and <span class="math-container">$b$</span> (putting <span class="math-container">$a$</span> to <span class="math-container">$T$</span> and <span class="math-container">$b$</span> to <span class="math-container">$S$</span>) would result in a larger cut, contradiction.</li>
</ul>
<p>Assume that <span class="math-container">$|S| = s, |T| = t$</span>. Let <span class="math-container">$x$</span> be the number of nodes from <span class="math-container">$S$</span> with cut-degree 2. Similarly, let <span class="math-container">$y$</span> be the number of nodes from <span class="math-container">$T$</span> with cut-degree 2.</p>
<p>Let <span class="math-container">$C$</span> be the size of the cut <span class="math-container">$(S, T)$</span>. Note that <span class="math-container">$C$</span> equals the sum of cut-degrees over the nodes from <span class="math-container">$S$</span>. Exactly <span class="math-container">$x$</span> nodes from <span class="math-container">$S$</span> have cut-degree <span class="math-container">$2$</span>. By observation 1 all the other nodes from <span class="math-container">$S$</span> have cut-degree at least <span class="math-container">$3$</span>. Hence
<span class="math-container">$$C \ge 2x + 3(s - x) = 3s - x.$$</span>
Applying a similar argument to the set <span class="math-container">$T$</span> we obtain:
<span class="math-container">$$C \ge 2y + 3(t - y) = 3t - y.$$</span>
Now, let us sum up the cut-degree over all nodes of <span class="math-container">$G$</span> with cut-degree 2. By observation 2 we never count an edge of the cut twice. Hence
<span class="math-container">$$C \ge 2x + 2y.$$</span>
By summing up these 3 inequalities with appropriate weights we obtain:
<span class="math-container">$$5C \ge 2(3s - x) + 2(3t - y) + 2x + 2y = 6(s + t) = 6n.$$</span>
This gives us <span class="math-container">$C \ge \lceil 6n/5\rceil$</span>. <strong>Proof of the Lemma is finished.</strong></p>

CC BY-SA 4.0
2020-08-14T15:42:20.747Z
That looks great!
smapers
CC BY-SA 4.0
2020-09-07T20:06:57.147Z
I think this response should be accepted, as it completely answers the question.
Mahdi Cheraghchi
CC BY-SA 4.0
2020-08-14T15:12:11.387Z
2020-08-14T15:12:11.387Z
Sasha Kozachinskiy
<p>Let us look at all 4-regular undirected graphs with <span class="math-container">$n$</span> nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its optimal solution. How would you construct that?</p>

CC BY-SA 4.0
2020-08-13T18:12:36.787Z
So you're asking what's the 4-regular graph on n vertices with the least possible max-cut?
Mahdi Cheraghchi
CC BY-SA 4.0
2020-08-13T18:26:27.150Z
@MahdiCheraghchi Yes!
Freiburger0
CC BY-SA 4.0
2020-08-13T18:31:06.757Z
Shouldn't it read "with least number of EDGES" instead of "with least number of CUTS"?
Gamow
<graph-theory><max-cut>
MaxCut instance with smallest max cut
Freiburger0
# MaxCut instance with smallest max cut

(Asked by: username_0 on 2020-08-13)

Let us look at all 4-regular undirected graphs with $n$ nodes and edge weight equals to 1 for all edges. Out of these graphs, I would like to find the MaxCut instance with least number of edges in its optimal solution. How would you construct that?

**Tags:** graph-theory, max-cut

> **Comments:**
> **username_1**: So you're asking what's the 4-regular graph on n vertices with the least possible max-cut?  
> **username_0**: @MahdiCheraghchi Yes!  
> **username_2**: Shouldn't it read "with least number of EDGES" instead of "with least number of CUTS"?  

---

## 1 answers

### Answer by username_3 on 2020-08-14. Score: 4

Take a clique of size 5 and consider a graph on $n = 5k$ nodes consisting of $k$ copies of this clique. The size of a maximal cut in this graph is $6k = 6n/5$. Indeed, from each copy we can maximally have 6 edges in a cut.

By the following lemma the size of a maximal cut can not be much smaller.

> **Lemma.** In any undirected 4-regular with $n$ nodes there exists a cut with at least $\lceil 6n/5 \rceil$ edges.

More precisely, for $n$ divisible by 5 the answer to your question is exactly $6n/5$. For other $n$ it can be a bit bigger, but only by a $O(1)$ term. Indeed, we can again consider a graph where all but $O(1)$ nodes are paritioned into copies of a 4-regular clique.

**Proof.** Let $G = (V, E)$ be a 4-regular graph with $n$ nodes and let $(S, T)$ be a maximal cut. For a node $a\in V$ let cut-degree of $a$ be the number of edges containing $a$ and belonging to the cut $(S, T)$. We rely on the following two easily verifiable observations:

* *Observation 1: any node has cut-degree at least 2.* Indeed, assume that $a\in V$ has cut degree at most $1$. WLOG, $a\in S$. Then removing $a$ from $S$ and putting it to $T$ would result in a larger cut, contradiction.
* *Observation 2: no edge of the cut connects two nodes with cut-degree 2.* Indeed, assume that nodes $a\in S$ and $b\in T$ are adjacent and both have cut-degree 2. Then swapping $a$ and $b$ (putting $a$ to $T$ and $b$ to $S$) would result in a larger cut, contradiction.

Assume that $|S| = s, |T| = t$. Let $x$ be the number of nodes from $S$ with cut-degree 2. Similarly, let $y$ be the number of nodes from $T$ with cut-degree 2.

Let $C$ be the size of the cut $(S, T)$. Note that $C$ equals the sum of cut-degrees over the nodes from $S$. Exactly $x$ nodes from $S$ have cut-degree $2$. By observation 1 all the other nodes from $S$ have cut-degree at least $3$. Hence
$$C \ge 2x + 3(s - x) = 3s - x.$$
Applying a similar argument to the set $T$ we obtain:
$$C \ge 2y + 3(t - y) = 3t - y.$$
Now, let us sum up the cut-degree over all nodes of $G$ with cut-degree 2. By observation 2 we never count an edge of the cut twice. Hence
$$C \ge 2x + 2y.$$
By summing up these 3 inequalities with appropriate weights we obtain:
$$5C \ge 2(3s - x) + 2(3t - y) + 2x + 2y = 6(s + t) = 6n.$$
This gives us $C \ge \lceil 6n/5\rceil$. **Proof of the Lemma is finished.**

> **Comments:**
> **username_4**: That looks great!  
> **username_1**: I think this response should be accepted, as it completely answers the question.  

---

