<p>By complementing the graph, this problem is a special case of the following problem:</p>
<blockquote>
<p><em>Given a graph <span class="math-container">$G=(V, E)$</span> and a desired degree <span class="math-container">$d_v$</span> for each vertex <span class="math-container">$v\in V$</span>, find a maximum-size subset <span class="math-container">$E'$</span> of <span class="math-container">$E$</span> such that each vertex <span class="math-container">$v\in V$</span> has at most <span class="math-container">$d_v$</span> edges in <span class="math-container">$E'$</span>.</em></p>
</blockquote>
<p>Polynomial-time algorithms for this problem (e.g. by reduction to maximum matching) are discussed in the paper &quot;Another look at the degree constrained subgraph problem&quot; by Yossi Shiloach, <a href="https://doi.org/10.1016/0020-0190(81)90009-0" rel="nofollow noreferrer">https://doi.org/10.1016/0020-0190(81)90009-0</a>.</p>

CC BY-SA 4.0
2022-12-18T22:30:36.020Z
Related: https://mathoverflow.net/questions/185475/existence-of-subgraphs-when-given-its-degree-sequence
Neal Young
CC BY-SA 4.0
2022-12-20T11:07:16.453Z
Thanks very much for your help... it was exactly what I was looking for!
jpcasti
CC BY-SA 4.0
2022-12-18T21:40:18.373Z
2022-12-18T22:09:23.470Z
2022-12-18T22:09:23.470Z
Neal Young
<p>My problem: <em>Given a graph <span class="math-container">$G=(V, E)$</span> and an integer <span class="math-container">$\ell$</span>,add a minimum number of edges to <span class="math-container">$G$</span> so that in the resulting graph every vertex has degree at least <span class="math-container">$\ell$</span>.</em></p>
<p>Is there a polynomial-time algorithm for this?  Is it NP-complete?</p>
<p>Thanks!</p>

<graph-theory><graph-algorithms><np-hardness>
increasing minimum graph degree by adding edges
jpcasti
# increasing minimum graph degree by adding edges

(Asked by: username_0 on 2022-12-18)

My problem: *Given a graph $G=(V, E)$ and an integer $\ell$,add a minimum number of edges to $G$ so that in the resulting graph every vertex has degree at least $\ell$.*

Is there a polynomial-time algorithm for this? Is it NP-complete?

Thanks!

**Tags:** graph-theory, graph-algorithms, np-hardness


---

## 1 answers

### Answer by username_1 on 2022-12-18. Score: 2 | Accepted answer

By complementing the graph, this problem is a special case of the following problem:

> *Given a graph $G=(V, E)$ and a desired degree $d\_v$ for each vertex $v\in V$, find a maximum-size subset $E'$ of $E$ such that each vertex $v\in V$ has at most $d\_v$ edges in $E'$.*

Polynomial-time algorithms for this problem (e.g. by reduction to maximum matching) are discussed in the paper "Another look at the degree constrained subgraph problem" by Yossi Shiloach, <https://doi.org/10.1016/0020-0190(81)90009-0>.

> **Comments:**
> **username_1**: Related: https://mathoverflow.net/questions/185475/existence-of-subgraphs-when-given-its-degree-sequence  
> **username_0**: Thanks very much for your help... it was exactly what I was looking for!  

---

