Bulgarian Winter Tournament

Lemma: Let $G$ be a connected graph with at least $3$ vertices. Then either there exist two vertices connected by an edge whose removal (along with the outgoing edges) leaves $G$ connected, or there exist two vertices of degree $1$ (i.e., "leaves"). Consider an arbitrary "covering tree" of $G$ and take as its "root" an arbitrary vertex that is not a "leaf". Let $v$ be the farthest vertex from the "root" and $u$ be its "ancestor". Let $v_1,v_2,\dots ,v_k$ be the "successors" of $u$. Clearly, they are all leaves on the tree.

Case 1. Among $v_1,v_2,\dots ,v_k$ there are two vertices connected by an edge in $G$. Then removing these two vertices leaves the tree (and therefore $G$) connected.

Case 2. Among $v_1,v_2,\dots ,v_k$ there are two vertices that are leaves in $G$. Then there are indeed at least two leaves in the output graph.

Case 3. Among $v_1,v_2,\dots ,v_k$ there is at most one vertex that is a leaf in $G$ (b.o.o., let it be $v_1$). Then let us "connect" each of $v_2,\dots ,v_k$ to an arbitrary vertex in $G$ other than $u$ (such vertices exist, and none of these "connecting" edges are part of the covering tree, due to the extreme choice of $u$, i.e., each of them is part of a loop, all remaining edges of which are from the covering tree). Now we can remove $u$ and $v_1$ and we will have a spanning tree again, so $G$ remains connected.

This proves the lemma. With its help we can easily prove the following

Assertion: Let $G$ be a connected graph with $n\ge 2$ vertices. Then we can color its vertices in two colors, so that if $x$ and $y$ are the number of "multicolored" and "single colored" edges, respectively, then $x-y\ge \lfloor \frac{n}{2}\rfloor$.

Proof: For $n=2,3$ the statement is immediately verified. Let $n\ge 4$ and $G$ be a connected graph with $n$ vertices. Let $u$ and $v$ be the two vertices from the Lemma. We "remove" $u$ and $v$ and color $G\setminus \{u,v\}$ according to the induction hypothesis. Now, it is not difficult to see that we can color $u\cup v$ such that the difference under consideration increases by at least $1$. Indeed, this is clear if $u$ and $v$ are leaves, and otherwise case, considering the parity of the number of neighbors of $u\cup v$ in $G\setminus \{u,v\}$, we see that there is always such a way. The statement is proved by induction.

Let us now consider an arbitrary connected graph $G$ with $n\ge 3$ vertices and $m$ edges. We "color" it according to the Assertion: we have $x-y\ge \lfloor \frac{n}{2}\rfloor$; $x+y=m$, therefore $$y\le \frac{1}{2}\cdot \left(m-\lfloor \frac{n}{2}\rfloor \right)$$ and deleting $y$ edges satisfies the condition. Thus, we got $k\le \frac{1}{2}$.

To show that $k\ge \frac{1}{2}$ let us consider the complete graph with $n$ vertices. A necessary and sufficient condition for having the coloring from the condition is that the graph obtained after deleting the edges is bipartite. Indeed, there must be no cycles of odd length in the graph, which is equivalent to the above.

Case 1. $n=2n_1$, $n_1\ge 2$. Then $m=\left(\genfrac{}{}{0ex}{}{n_1}{2}\right)$. To reach a bipartite graph, we need to delete all the edges in each of the two groups of vertices, and the number of deleted edges is minimal when the two groups are of equal power and contain $n_1$ vertices. So, we need to delete at least $$\left(\genfrac{}{}{0ex}{}{n_1}{2}\right)+\left(\genfrac{}{}{0ex}{}{n_1}{2}\right)=n_1^2-n_1$$ $$n_1^2-n_1\le k\cdot \left(\frac{2n_1(2n_1-1)}{2}-n_1\right)⟹k\ge \frac{1}{2}.$$

Case 2. $n=2n_1+1$, $n_1\ge 1$. Similarly, here we need to delete at least $$\left(\genfrac{}{}{0ex}{}{n_1+1}{2}\right)+\left(\genfrac{}{}{0ex}{}{n_1}{2}\right)=n_1^2$$ edges and again $$ n_1^2 \le k \cdot \left( \frac{2n_1(2n_1+1)}{2} - n_1 \right) \implies k \ge \frac{1}{2}. \quad \square