Could someone check this? I am not so sure about the correctness of my solution.

starchan wrote: $|E(G')| \geqslant |v(G')|-1$. Well I don't think this necessarily implies that $G'$ is connected.

hakN wrote: starchan wrote: $|E(G')| \geqslant |v(G')|-1$. Well I don't think this necessarily implies that $G'$ is connected. True but $G$ was connected before. Maybe that saves it? I am still not sure.

Solved with TWN 2021 members: The trickiest part is to realize that the statement can be strengthened. In fact, we can show that if $d>3$, $G$ is a connected simple graph that is not an isolated point, \[x_d\geq x_{d-1}+\cdots+(d-2)x_2+(d-2)x_1-d\]and there does not exist a vertex $v$ with degree $d$ such that $G-v$ is connected, then the equality holds and $G$ has vertices only of degrees with $1,d-1,d$. We first deal with the case $x_d=0$ and show that in this case $G$ is either an edge or $K_d$. In fact, if there are $n$ vertices and $m$ edges, then \[-x_1+\sum_{i=1}^{d-1}(d-i)x_i\geq (n-x_1)+(d-2)x_1=n+(d-3)x_1\]and \[-x_1+\sum_{i=1}^{d-1}(d_i)x_i\geq dn-2m-x_1\geq dn-(n-x_1)(n-x_1-1)-3x_1=n(d+2x_1+1-n)-x_1^2-4x_1.\]Therefore we just need to deal with the case when $n+(d-3)x_1\leq d$. If $x_1=0$, then in this case, we have $n(d+1-n)>d$ unless $n=1, d$. Since $G$ is not an isolated vertex, we have that $n=d$ and all the equality has to hold. This shows that $G$ is the complete graph on $d$ vertices, as desired. If $x_1=1$, then $n\geq 2$ and $n(d+2x_1+1-n)\geq \min(2(d+1), 3d)=2d+2$ and so $n(d+2x_1+1-n)-x_1^2-4x_1\geq 2d-3>d.$ If $x_1=2$, then $n+(d-3)x_1\leq d$ implies that $d=4, n=x_1=2$ and so $n(d+2x_1+1-n)-x_1^2-4x_1\geq 2d-3=d.$ In this case we get an edge. If $x_1\geq 3$, then $3(d-2)\leq d$, showing that $d\leq 3$, which is a contradiction. For larger $x_d$, we use induction and assume that the above claims hold for smaller $x_d$. We take an arbitrary vertex $v$ with degree $d$ in $G$. $G-v$ is not connected by assumption, so let us assume that $G-v$ has components $G_1,\ldots,G_k$ where $k\geq 2$. For each $G_i$, we add $v$ back, label this $v$ as $v_i$ and call this new graph $G_i'$. It is clear that there does not exist any $u\in G_i'$ with $\deg u=d$ such that $G_i'-u$, for otherwise we can take this $u$ in $G$. Let $x^i_j$ be the number of vertices in $G_i'$ with degree $j$. Then we can see that \[\sum_{i=1}^{k}x^i_j=x_j-\#\{i|\deg v_i=j\}\]if $j\leq d-1$ and \[\sum_{i=1}^{k}x^i_d=x_d-1.\]Therefore we have \[\sum_{i=1}^{k}\left(-x^i_d-x^i_1+\sum_{j=1}^{d-1}(d-j)x^i_j\right)\]\[=-x_d+1-x_1+\sum_{j=1}^{d-1}(d-j)x_j-\sum_{i=1}^{k}(d-\deg(v_i))-\#\{i|\deg(v_i)=1\}\]\[\leq -dk+1-\#\{i|\deg(v_i)=1\}\]where we use the inequality in the assumption and the fact that $\sum_{i=1}^{k}\deg(v_i)=d$. As $k\geq 2$, this shows that there exists a choice $i$ such that $x^i_d\geq x^i_{d-1}+\cdots+(d-2)x^i_2+(d-2)x^i_1-d$. By the inductive hypothesis, we know that $\deg v_i=1$ or $d-1$. If $\deg v_i=d-1$ then clearly $k=2$ and $\deg v_{k+1-i}=1$. In any case we have $\#\{i|\deg(v_i)=1\}\geq 1$, and so \[\sum_{i=1}^{k}\left(-x^i_d-x^i_1+\sum_{j=1}^{d-1}(d-j)x^i_j\right)\leq -dk.\]Therefore we must have that \[\left(-x^i_d-x^i_1+\sum_{j=1}^{d-1}(d-j)x^i_j\right)\leq -d\]holds for all $i=1,\ldots,k$, and by the inductive hypothesis we have $G_i'$ only has vertices of degrees $1,d-1,d$. Hence $G$ also only has vertices of degrees $1,d-1,d$, as desired. We thus have proved the claim by induction. The problem statement then follows immediately as a corollary.

Also, am I just being stupid by not realizing an easier solution, or is this problem just extremely hard? Problem 3 also seems extremely hard lol. I would've cried if I were one of the contestants.

USJL wrote: I would've cried if I were one of the contestants. we all did , @bellow yeah i was one of them

Mr.C wrote: USJL wrote: I would've cried if I were one of the contestants. we all did Oof this might be off topic, but were you one of the contestants by any chance? I'm kinda curious about how the cutoff would turn out to be lol.

Mr.C wrote: USJL wrote: I would've cried if I were one of the contestants. we all did , @bellow yeah i was one of them Ah I see. I'd appreciate it if you tell us the cutoff if that's available to you then. Also best of luck for you!

I think the following solution works. We will induct on the number of vertices, $n$. When $n<d+1$, there is nothing to prove. Suppose the claim is true for all $k<n$. Consider a graph $G$ which satisfies the condition which has $n$ vertices. Suppose that removing any vertex with degree $d$ disconnects the graph. Then each of the $x_d$ vertices induces a partition of the remaining vertices into connected components. Pick a vertex $v$ in which the largest element of such partition is the largest possible. Let $C$ be the mentioned largest component and let $D$ be the union of remaining components. We now claim that any element of $D$ has degree less than $d$. Suppose, for the sake of contradiction, that some $x$ from $D$ has degree $d$. Then we notice that $v+C$ is a subset of some connected component of a graph obtained from $G$ by removing $x$, which is a contradiction with the maximality of $C$. Thus the claim is proven. Now we will prove that either $C$ or $v+C$ satisfies the condition of the problem, which is enough because of our induction assumption. Let $s$ be the number of neighbours of $v$ in $D$. Then $v$ has degree $d-s$ in $v+C$, and the number of vertices with degree $d$ equals $x_d-1$. This decreases the left side by $1$ and increases the right side by $s$. On the other hand, there are at least $s$ vertices in $D$. If there are more than $s$ of them, $v+C$ satisfies the condition since removal of each of them decreases the right side by at least $1$. If there are exactly $s$ of them, their degree (in $G$) is at most $s$, and they decrease the right side by at least $s(d-s)$. If $d-s>1$, then $v+C$ also satisfies the condition. The only remaining case is the one in which $s=d-1$ and each of the vertices has degree $d-1$. In that case, $v$ has exactly one neighbour in $C$, say $w$, and $D+v$ is a clique with $d$ vertices. Now, the number of vertices with degree $d$ in $C$ equals $x_d-2$ (since $v$ is erased and $w$ now has degree $d-1$), and the number of vertices with degree $d-1$ in $C$ equals $x_{d-1}-(d-1)+1=x_{d-1}-d+2$, since we erased $d-1$ of them, and $w$ now has degree $d-1$. Since $d\geq 4$, we conclude $C$ satisfies the conditions. In each case, we reached a graph with less than $n$ vertices which satisfies the condition but removing any vertex of degree $d$ disconnects the graph, a contradiction. This completes the inductive step.

square_root_of_3 wrote: I think the following solution works. We will induct on the number of vertices, $n$. When $n<d+1$, there is nothing to prove. Suppose the claim is true for all $k<n$. Consider a graph $G$ which satisfies the condition which has $n$ vertices. Suppose that removing any vertex with degree $d$ disconnects the graph. Then each of the $x_d$ vertices induces a partition of the remaining vertices into connected components. Pick a vertex $v$ in which the largest element of such partition is the largest possible. Let $C$ be the mentioned largest component and let $D$ be the union of remaining components. We now claim that any element of $D$ has degree less than $d$. Suppose, for the sake of contradiction, that some $x$ from $D$ has degree $d$. Then we notice that $v+C$ is a subset of some connected component of a graph obtained from $G$ by removing $x$, which is a contradiction with the maximality of $C$. Thus the claim is proven. Now we will prove that either $C$ or $v+C$ satisfies the condition of the problem, which is enough because of our induction assumption. Let $s$ be the number of neighbours of $v$ in $D$. Then $v$ has degree $d-s$ in $v+C$, and the number of vertices with degree $d$ equals $x_d-1$. This decreases the left side by $1$ and increases the right side by $s$. On the other hand, there are at least $s$ vertices in $D$. If there are more than $s$ of them, $v+C$ satisfies the condition since removal of each of them decreases the right side by at least $1$. If there are exactly $s$ of them, their degree (in $G$) is at most $s$, and they decrease the right side by at least $s(d-s)$. If $d-s>1$, then $v+C$ also satisfies the condition. The only remaining case is the one in which $s=d-1$ and each of the vertices has degree $d-1$. In that case, $v$ has exactly one neighbour in $C$, say $w$, and $D+v$ is a clique with $d$ vertices. Now, the number of vertices with degree $d$ in $C$ equals $x_d-2$ (since $v$ is erased and $w$ now has degree $d-1$), and the number of vertices with degree $d-1$ in $C$ equals $x_{d-1}-(d-1)+1=x_{d-1}-d+2$, since we erased $d-1$ of them, and $w$ now has degree $d-1$. Since $d\geq 4$, we conclude $C$ satisfies the conditions. In each case, we reached a graph with less than $n$ vertices which satisfies the condition but removing any vertex of degree $d$ disconnects the graph, a contradiction. This completes the inductive step. $w$ may be not a degree $d$ vertex in $G$. Anyway, it loses 1 degree so contributes to the inequality by -1(case deg(w)<d) or -2(case deg(w)=d) while the $D+ v$ part contributes $d-2$. Hence the inequality holds as $d\ge 4$.

We use induction on the number of vertices. Suppose $G$ has $n$ vertices and $e$ edges. Note that our condition is equivalent to $x_d \ge \displaystyle\sum_{i=1}^{d-1} (d-i)x_i = d\displaystyle\sum_{i=1}^{d-1}x_i - \displaystyle\sum_{i=1}^{d-1}ix_i = d(n-x_d) -(2e - dx_d) = dn -2e$ Or equivalently $2e \ge dn -2e.$ We use induction on the number of vertices. Note that for $n=3$ we have that the only graph satisfying problem condition is a $K_3$ which also satisfies problem claim. Now suppose our claim is true for all number less than $n$ but assume for contradiction that it is false for $n$. Then let $v$ be any vertice of $G$ with $d(v)=d;$ and suppose that the resulting graph after removing $v$ has $k$ connected components (namely $C_1,C_2,...C_k$) where $k>1.$ Let $G_i = C_i +v$ and suppose it has $n_i$ vertices, $e_i$ edges and ${x_d}^i$ vertices with degree $d.$ If ${x_d}^i = 0$ then every vertice has degree lesser than $d$ and hence $2e_i<dn_i = dn_i -{x_d}^i.$ If ${x_d}^i>0$ then let $u$ be a vertice with degree $d$ (both in $G$ and in $G_i$); then note that removing $u$ of $G$ desconnects $G$ iff it desconects $G_i.$ But by our contradiction hipothesis it does desconnects $G$ then it desconnects $G_i$ and hence, since $V(G_i)< V(G),$ by our induction hipothesis we have $2e_i < dn_i - {x_d}^i.$ Then we conclude that $2e_i < dn_i -{x_i}^d$ for every $1\le i \le k$ and hence $2\displaystyle\sum_{i=1}^{k} e_i < d\displaystyle\sum_{i=1}^{k} n_i - \displaystyle\sum_{i=1}^{k} {x_d}^i \iff 2e < d(n-(k-1)) -(x_d -1) \le dn - x_d$ Which yelds a contradiction with our hipothesis (the last inequality was obtained by $k\ge 2$).

PHSH wrote: Then we conclude that $2e_i < dn_i -{x_i}^d$ for every $1\le i \le k$ and hence $2\displaystyle\sum_{i=1}^{k} e_i < d\displaystyle\sum_{i=1}^{k} n_i - \displaystyle\sum_{i=1}^{k} {x_d}^i \iff 2e < d(n-(k-1)) -(x_d -1) \le dn - x_d$ Which yelds a contradiction with our hipothesis (the last inequality was obtained by $k\ge 2$). it has a mistake , hence $G_i=C_i +v $ , the vertice v has been counted k times $\sum\limits_{i=1}^{k} n_i = n+(k-1)$ ,

xst wrote: PHSH wrote: Then we conclude that $2e_i < dn_i -{x_i}^d$ for every $1\le i \le k$ and hence $2\displaystyle\sum_{i=1}^{k} e_i < d\displaystyle\sum_{i=1}^{k} n_i - \displaystyle\sum_{i=1}^{k} {x_d}^i \iff 2e < d(n-(k-1)) -(x_d -1) \le dn - x_d$ Which yelds a contradiction with our hipothesis (the last inequality was obtained by $k\ge 2$). it has a mistake , hence $G_i=C_i +v $ , the vertice v has been counted k times $\sum\limits_{i=1}^{k} n_i = n+(k-1)$ , Yep. I guess you're right and it is not fixable. This was exactly three years ago, lol.

PHSH wrote: xst wrote: PHSH wrote: Then we conclude that $2e_i < dn_i -{x_i}^d$ for every $1\le i \le k$ and hence $2\displaystyle\sum_{i=1}^{k} e_i < d\displaystyle\sum_{i=1}^{k} n_i - \displaystyle\sum_{i=1}^{k} {x_d}^i \iff 2e < d(n-(k-1)) -(x_d -1) \le dn - x_d$ Which yelds a contradiction with our hipothesis (the last inequality was obtained by $k\ge 2$). it has a mistake , hence $G_i=C_i +v $ , the vertice v has been counted k times $\sum\limits_{i=1}^{k} n_i = n+(k-1)$ , Yep. I guess you're right and it is not fixable. This was exactly three years ago, lol. but i don't find a solution that i can understand yet.