# MaxCut instance with smallest max cut

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?

• So you're asking what's the 4-regular graph on n vertices with the least possible max-cut? – Mahdi Cheraghchi Aug 13 '20 at 18:12
• @MahdiCheraghchi Yes! – Freiburger0 Aug 13 '20 at 18:26
• Shouldn't it read "with least number of EDGES" instead of "with least number of CUTS"? – Gamow Aug 13 '20 at 18:31

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.

• That looks great! – smapers Aug 14 '20 at 15:42
• I think this response should be accepted, as it completely answers the question. – Mahdi Cheraghchi Sep 7 '20 at 20:06