Recently, a mathematical olympiad problem is proposed as follows:

Let $G$ be a graph with $|V| = 100$ and $\delta(G) \geqslant 10$. Prove that there is an integer $0 \leqslant k \leqslant 5$, such that there is a vertex partition $V = A \cup B$, where $|A| = 50 + k$ and $|B| = 50 - k$, as well as $d_A(x) \geqslant 5 + k$, $x \in A$, and $d_B(y) \geqslant 5 - k$, $y \in B$.

It occurs to me the classical result by Stiebitz. (Stiebitz, M. (1996). Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3), 321-324.)

If $G$ is a graph with minimum degree $s + t + 1$, then $G$ has a vertex partition $V = S \cup T$ such that $d_S(x) \geqslant s$, $x \in S$ and $d_T(y) \geqslant t$, $y \in T$.

This result has several improvements. If $G$ is $K_3$-free, $s + t + 1$ can be reduced to $s + t$. (Kaneko, 1998) If $G$ is $C_4$-free, it can be reduced to $s + t - 1$. (Ma, 2019)

Obviously, the original theorem fails to provide a partition satisfying the degree condition. And the improvements are not available for the problem since $|V| = 100$ and $\delta(G) \geqslant 10$ force the girth to be less than $5$. Therefore despite the seemingly strong connection between this olympiad theorem and the $(a,b)$-feasible partition topic, the problem doesn't coincide with the research interest of the topic.

I question whether similar conclusions can be used to solve this olympiad problem, in case I missed some relevant theorems. If not, could the spirit of establishing this series of theorems be applied to this olympiad problem?

By the way, the olympiad problem requires a 'near-bisection' condition, which seems rare among $(a,b)$-feasible partition problems, while hot in friendly partition topics. Is there some literature progressing on this aspect of $(a,b)$-feasible partition problems?

(I posted this in math stack exchange a few hours ago but I am afraid it's more suitable for math overflow, and I repost it here therefore. )

Recently, a mathematical olympiad problem is proposed as follows:

Let $G$ be a graph with $|V| = 100$ and $\delta(G) \geqslant 10$. Prove that there is an integer $0 \leqslant k \leqslant 5$, such that there is a vertex partition $V = A \cup B$, where $|A| = 50 + k$ and $|B| = 50 - k$, as well as $d_A(x) \geqslant 5 + k$, $x \in A$, and $d_B(y) \geqslant 5 - k$, $y \in B$.

It occurs to me the classical result by Stiebitz. (Stiebitz, M. (1996). Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3), 321-324.)

If $G$ is a graph with minimum degree $s + t + 1$, then $G$ has a vertex partition $V = S \cup T$ such that $d_S(x) \geqslant s$, $x \in S$ and $d_T(y) \geqslant t$, $y \in T$.

This result has several improvements. If $G$ is $K_3$-free, $s + t + 1$ can be reduced to $s + t$. (Kaneko, 1998) If $G$ is $C_4$-free, it can be reduced to $s + t - 1$. (Ma, 2019)

Obviously, the original theorem fails to provide a partition satisfying the degree condition. And the improvements are not available for the problem since $|V| = 100$ and $\delta(G) \geqslant 10$ force the girth to be less than $5$. Therefore despite the seemingly strong connection between this olympiad theorem and the $(a,b)$-feasible partition topic, the problem doesn't coincide with the research interest of the topic.

I question whether similar conclusions can be used to solve this olympiad problem, in case I missed some relevant theorems. If not, could the spirit of establishing this series of theorems be applied to this olympiad problem?

By the way, the olympiad problem requires a 'near-bisection' condition, which seems rare among $(a,b)$-feasible partition problems, while hot in friendly partition topics. Is there some literature progressing on this aspect of $(a,b)$-feasible partition problems?

(I posted this in math stack exchange a few hours ago but I am afraid it's more suitable for math overflow, and I repost it here therefore. )

Recently, a mathematical olympiad problem is proposed as follows:

Let $G$ be a graph with $|V| = 100$ and $\delta(G) \geqslant 10$. Prove that there is an integer $0 \leqslant k \leqslant 5$, such that there is a vertex partition $V = A \cup B$, where $|A| = 50 + k$ and $|B| = 50 - k$, as well as $d_A(x) \geqslant 5 + k$, $x \in A$, and $d_B(y) \geqslant 5 - k$, $y \in B$.

It occurs to me the classical result by Stiebitz. (Stiebitz, M. (1996). Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3), 321-324.)

If $G$ is a graph with minimum degree $s + t + 1$, then $G$ has a vertex partition $V = S \cup T$ such that $d_S(x) \geqslant s$, $x \in S$ and $d_T(y) \geqslant t$, $y \in T$.

This result has several improvements. If $G$ is $K_3$-free, $s + t + 1$ can be reduced to $s + t$. (Kaneko, 1998) If $G$ is $C_4$-free, it can be reduced to $s + t - 1$. (Ma, 2019)

Obviously, the original theorem fails to provide a partition satisfying the degree condition. And the improvements are not available for the problem since $|V| = 100$ and $\delta(G) \geqslant 10$ force the girth to be less than $5$. Therefore despite the seemingly strong connection between this olympiad theorem and the $(a,b)$-feasible partition topic, the problem doesn't coincide with the research interest of the topic.

I question whether similar conclusions can be used to solve this olympiad problem, in case I missed some relevant theorems. If not, could the spirit of establishing this series of theorems be applied to this olympiad problem?

By the way, the olympiad problem requires a 'near-bisection' condition, which seems rare among $(a,b)$-feasible partition problems, while hot in friendly partition topics. Is there some literature progressing on this aspect of $(a,b)$-feasible partition problems?

(I posted this in math stack exchange a few hours before but I am afraid it's more suitable for math overflow, so I repost it here. )

Recently, a mathematical olympiad problem is proposed as follows:

Let $G$ be a graph with $|V| = 100$ and $\delta(G) \geqslant 10$. Prove that there is an integer $0 \leqslant k \leqslant 5$, such that there is a vertex partition $V = A \cup B$, where $|A| = 50 + k$ and $|B| = 50 - k$, as well as $d_A(x) \geqslant 5 + k$, $x \in A$, and $d_B(y) \geqslant 5 - k$, $y \in B$.

It occurs to me the classical result by Stiebitz. (Stiebitz, M. (1996). Decomposing graphs under degree constraints. Journal of Graph Theory, 23(3), 321-324.)

If $G$ is a graph with minimum degree $s + t + 1$, then $G$ has a vertex partition $V = S \cup T$ such that $d_S(x) \geqslant s$, $x \in S$ and $d_T(y) \geqslant t$, $y \in T$.

This result has several improvements. If $G$ is $K_3$-free, $s + t + 1$ can be reduced to $s + t$. (Kaneko, 1998) If $G$ is $C_4$-free, it can be reduced to $s + t - 1$. (Ma, 2019)

Obviously, the original theorem fails to provide a partition satisfying the degree condition. And the improvements are not available for the problem since $|V| = 100$ and $\delta(G) \geqslant 10$ force the girth to be less than $5$. Therefore despite the seemingly strong connection between this olympiad theorem and the $(a,b)$-feasible partition topic, the problem doesn't coincide with the research interest of the topic.

I question whether similar conclusions can be used to solve this olympiad problem, in case I missed some relevant theorems. If not, could the spirit of establishing this series of theorems be applied to this olympiad problem?

By the way, the olympiad problem requires a 'near-bisection' condition, which seems rare among $(a,b)$-feasible partition problems, while hot in friendly partition topics. Is there some literature progressing on this aspect of $(a,b)$-feasible partition problems?

(I posted this in math stack exchange a few hours ago but I am afraid it's more suitable for math overflow, and I repost it here therefore. )