An optimal procedure for vertex elimination in a graph Figure: An example of my problem

Hi everyone. I'm struggling with a problem, and I really appreciate any hint.
I have attached picture of an example where vertex 1 and 2 are connected to multiple vertices (green circles and blue squares). I want to gradually eliminate some of these blue and green vertices such that the number of edges connected to vertex 1 or 2 does not exceed 4. Also, my objective is doing this with the minimum number of eliminations. So, let's define it mathematically. If $d_B$ and $d_G$ respectively denote the number of remaining blue squares and green circles after elimination, and also if $d_i$ denotes the connected edges to vertex $i$ after elimination,  my problem is how to organize an optimal elimination procedure such that it maximizes $min(d_B,d_G)$ while it satisfies $d_i\leq4$ for $i=1,2$.
 A: Here is a formulation using integer programming (IP). 
Sets and Parameters:


*

*$G$ = set of green vertices

*$B$ = set of blue vertices

*$N$ = set of all vertices ($=G\cup B$)

*$a_{kn} = 1$ if black vertex $k$ ($k\in\{1,2\}$) in the original network, $0$ otherwise


Decision Variables:


*

*$x_n = 1$ if we remove vertex $n\in N$, $0$ otherwise

*$y = $ minimum (over {blue,green}) number of vertices in each group


Formulation:
$$\begin{alignat}{2}
\text{maximize} \quad & y && \\
\text{subject to} \quad & y \le \sum_{b\in B} (1-x_b) \\
& y \le \sum_{g\in G} (1-x_g) \\
& \sum_{n \in N} a_{kn}(1-x_n) \le 4 &\quad& \forall k\in \{1,2\} \\
& x_n \in \{0,1\} && \forall n\in N
\end{alignat}$$
The objective function maximizes the minimum number of vertices in each group (what you called $min(d_B,d_G)$ in your question). The first two constraints say that $y$ (the minimum) must be less than or equal to each of the vertex sets, after removals. (Note that $1-x_b$ and $1-x_g$ equal 1 if we don't remove the node and 0 if we do.) The third constraint says that for each black vertex $k$, the total number of edges that are connected to $k$ ($a_{kn}=1$) and are attached to a vertex that has not been removed ($1-x_n$) must be less than or equal to 4.
Now you can code this in your modeling language of choice and solve it with any IP solver.
A: Definitions:


*

*$d_1^s = d_{1B}^s +  d_{1G}^s$ the number of single edges to vertex 1: $d_{1B}$ and $d_{1G}$ are the number of single edges blue and green to vertex 1, respectively.

*$d_2^s= d_{2B}^s + d_{2G}^s$ the number of single edges to vertex 2.

*$d^d= d_{B}^d + d_{G}^d$ the number of double edges.
Now,


*

*The number of vertexs blue and green will be:
$$N_B = d_{1B}^s + d_{2B}^s + d_{B}^d$$
$$N_G = d_{1G}^s + d_{2G}^s + d_{G}^d$$

*The number of edges to vertexs 1 and 2 will be:
$$d_1 = d_1^s + d^d = d_{1B}^s + d_{1G}^s + d_{B}^d + d_{G}^d$$
$$d_2 = d_2^s + d^d = d_{2B}^s + d_{2G}^s + d_{B}^d + d_{G}^d$$
We can see:
$$ N_B + N_G = d_1 + d_2 - d^d $$
Aims:
We are asked for an algorithm to get $d_1 \leq 4$ and $d_2 \leq 4$ as well as $N_B$ and $N_G$ subject to being the maximum value of $\text{min} (N_B, N_G)$.
We consider the case $d_1 = 4$ and $d_2 = 4$ and look for the maximum value of $\text{min} (N_B, N_G)$ subject to $ N_B + N_G = 8 - d^d $. The solution to this optimization problem is $N_B = N_G = \frac{8 - d^d}{2}$, but because they are integers, sometimes this is not possible, and our aim is to get:
$$N_B = 4-\left.\frac{ d^d}{2}\right|_{\mathcal{Z}_{\text{sgn}(d_G^d-d_B^d)}}$$
$$N_G = 4-\left.\frac{d^d}{2}\right|_{\mathcal{Z}_{\text{sgn}(d_B^d-d_G^d)}}$$
where $x|_{\mathcal{Z}_+}$ is rounding the real $x$ to the next integer and $x|_{\mathcal{Z}_-}$ is rounding the real $x$ to the previous integer. We introduce this condition because if $d_G^d-d_B^d > 0$ sometimes it will be the only option to get $N_G = N_B + 1$ (for example if $d_G^b = 3$ and $d_B^b = 0$, we can only get $N_G = 3$ and $N_B = 2$).
Algorithm:
All this means that first, we will try to remove all possible double edges, because they decrease the final $N_B$ and $N_G$ which decrease $\text{min} (N_B, N_G)$. But also, keeping a similar number of $d_G^d \sim d_B^d$, because if we have only $4$ double edges of the same color, the other colour will have $0$ vertices at the end and $\text{min} (N_B, N_G) = 0$. I leave the practical implementation for you to think. Keep in mind also the cases when you are starting already with $d_1 + d_2 <8$, which would change the aiming condition. 
