a (g,f)-factor puzzle

Question

Given a graph $G$, and a pair of integers $(g_i, f_i)$ for each node $i$, that denotes the min and max desirable degree for that node, a solution is a subgraph of $G$ in which the degree of each node is between $g_i$ and $f_i$. Figure below shows an example and three different solutions.

Prove that if there exists two solutions ($G_0,G_1$) in which the degrees of three selected nodes (denoted as $X,Y,Z$) are $(0,0,0)$ in $G_0$ and $(1,1,1)$ in $G_1$ then there would exist at least one other solution ($G_2$) in which degrees of $X,Y,Z$ is neither $(0,0,0)$ nor $(1,1,1)$.

Answer 1

Initialize $G_2=G_0 + xu$ where $u$ is the node connected to $x$ in $G_1$.

step 1: If degree of $u$ in $G_2$ is not satisfied, switch $uv$ in $G_2$, where $uv$ is an edge that is different between $G_2$ and $G_1$ to satisfy $u$ in $G_2$; then repeat this step for $v$.

This algorithm eventually stops as the number of edges that differ between $G_2$ and $G_1$ reduces in every step. Moreover, if at some point, we reach either node $y$ or $z$, the algorithm stops, hence the degree of either $y$ or $z$ would remain $0$ in the final $G_2$.

Answer 2

Starting at the vertex $x$, take a walk in $G$ that obeys the following rules for as long as possible:

• On every odd-numbered step, including the first step, take an edge of $G_1$ that is not in $G_0$ (and that we haven't previously taken).
• On every even-numbered step, take an edge of $G_0$ that is not in $G_1$ (and that we haven't previously taken).
• Stop as soon as no such edge exists.

Let $W$ be the set of all edges along the walk. Note that the walk includes at least one edge out of $x$, because we can always take the first step. Also, the walk cannot return to $x$ (there is only one edge of $G_0$ or $G_1$ incident to $x$) so it ends at some other vertex $t \ne x$.

Then, define $G_2$ as follows:

• If we stopped after an even number of steps, let $G_2$ be the subgraph of $G$ whose edge set is $E(G_2) = E(G_0) \mathbin{\Delta} W$.
• If we stopped after an odd number of steps, let $G_2$ be the subgraph of $G$ whose edge set is $E(G_2) = E(G_1) \mathbin{\Delta} W$.

(Here, $\Delta$ denotes the symmetric difference: for every edge in $W$, we add it if it wasn't included, and remove it if it was.)

---

Claim 1. $G_2$ is an $(f,g)$-factor of $G$.

Proof. Let's suppose that we're in the case where $E(G_2) = E(G_0) \mathbin{\Delta} W$ (the proofs for the two cases are very similar). Then, the endpoint $t$ has no edges of $G_1$ that are not in $G_0$, except for edges already in $W$.

At every vertex $v \ne x,$, we have $\deg_{G_2}(v) = \deg_{G_0}(v)$. So $G_2$ is still an $(f,g)$-factor at those vertices. At $x$, the degree went up from $0$ to $1$, but we know that $f_x = 0$ and $g_x \ge 1$, so this is still valid.

At $t$, the degree went down by $1$: the last step into $t$ was an edge of $G_0$ not in $G_1$, and on any previous occasions when we visited $t$, we took an edge of both graphs. However, $t$'s degree in $G_0$ is greater than $t$'s degree in $G_1$: among edges of $W$, $t$ is incident to more edges of $E(G_0) \cap W$ than $E(G_1) \cap W$, and among edges outside $W$, $t$ is not incident to any edge of $G_1$ that isn't also in $G_0$. So in $G_2$, $t$'s degree is still at least what it is in $G_1$. Therefore $G_2$ is still an $(f,g)$-factor.

Claim 2. In $G_2$, the degrees $(\deg(x), \deg(y), \deg(z))$ are neither $(0,0,0)$ nor $(1,1,1)$.

Proof. To arrive at $G_2$, we start at either $G_0$ or $G_1$, and only two vertex degrees change: $\deg(x)$ and $\deg(t)$. The endpoint $t$ might be one of $y$ or $z$, or it might not be. However, at least one of $\{x,y,z\}$ changes its degree ($x$ definitely does) and at least one keeps the same degree, so not all three degrees are equal in $G_2$.