In other words, we are asked to show we can remove (at least) $\dfrac{n(n-1)}{2}$ edges of a connected graph $G = (V,E)$, with chromatic number $\chi(G) > n$, so that $G$ remains connected. Although, most likely, the problem refers to finite graphs, the de Bruijn - Erdös theorem allows the consideration of infinite graphs as well. Theorem.An infinite graph $G$ can be coloured with $k$ colours (so that adjacent vertices bear different colour) if and only if any finite subgraph of it can be thus coloured with $k$ colours. As a consequence, if $G$ is infinite, with $\chi(G) > n$, then there exists a finite subgraph $H$ of it, with $\chi(H) > n$ (the issue of the connectedness of $H$ is moot, since we may consider its connected component of maximal chromatic number, which must be larger than $n$). We then remove $\dfrac{n(n-1)}{2}$ edges from $H$, and since $G$ was connected, putting back the vertices from $G - H$ keeps the graph connected. In the sequel we will therefore assume $G$ is finite. Let $m$ be the number of edges of a finite graph $G$; then \[\chi(G) \leq \dfrac {1} {2} + \sqrt{2m +\dfrac {1} {4}}.\] Proof. Let be a colouring of $G$ with $k=\chi(G)$ colours. Then $G$ has at least one edge connecting any two colour classes; otherwise we could use a same colour for both classes. Therefore $m\geq \dfrac {k(k-1)} {2}$, the very conclusion we desired. Another (trivial) result is $\chi(G) \leq \Delta(G) + 1$, where $\Delta(G)$ is the largest degree of a vertex of $G$. In our case we therefore have $m \geq \dfrac {n(n+1)} {2} = \dfrac {n(n-1)} {2} + n$, and at least we now know a graph with $\chi(G)\geq n+1$ has enough edges so we can remove $\dfrac{n(n-1)}{2}$ of them. On the other hand, we also have $\Delta(G) \geq n$. Let us notice that $\dfrac{n(n-1)}{2}$ is the largest value generally possible; for $G=K_{n+1}$ (the complete graph on $n+1$ vertices $v_1,v_2,\ldots,v_n,v_{n+1}$) we can remove $\displaystyle \binom {n+1} {2} - n = \dfrac{n(n-1)}{2}$ edges (being left with the (connected) Hamiltonian path $v_1v_2\ldots v_nv_{n+1}$ with $n$ edges), but not more. The solution goes by induction on $|G| + n$. Initial cases are trivial, so we pass right to the induction step. It is easy to see there exists a vertex $v$ which does not disconnect the graph when removed. Let $G - v$. If $\chi(G - v) > n$, then by the induction hypothesis we may remove from $G - v$ a set $M$ of edges, having $|M| \geq \dfrac{n(n-1)}{2}$, so that the graph remains connected, but then the graph $G' = (V, E\setminus M)$ will also be connected. Otherwise, since $\chi(G - v) \geq \chi(G) - 1 > n-1$ (in fact then $\chi(G - v) = n$), we may remove from $G - v$ a set $M$ of edges, having $|M| \geq \dfrac{(n-1)(n-2)}{2}$. But clearly $\deg v \geq n$, so we may remove at least $n-1$ edges incident at $v$ from $G' = (V, E\setminus M)$, which therefore remains connected after the removal of (at least) $\dfrac{(n-1)(n-2)}{2} + (n-1) = \dfrac{n(n-1)}{2}$ edges.

Another solution: we color the graph by going through each vertex individually. Pick an arbitrary vertex and give it color number $1$. Then at each step, choose another vertex adjacent to at least one vertex we've colored already, and give it the smallest number color that is valid. Furthermore, each time we give a vertex $v$ a color $k$, we know it is adjacent to colors $1, 2, \ldots, k-1$. If $k \geq 3$, erase the edges connecting $v$ to vertices of color greater than $1$; the graph is still connected. At the end, we've used all of the colors $1, 2, 3, \ldots, n+1$ at least once, so we've erased at least $1 + 2 + 3 + \cdots + (n-1)= \dfrac {n(n-1)} {2}$ edges. The final graph is still connected, so we're done.

The above is based in essence on the following Proposition 1.4.1. [Reinhard Diestel - Graph Theory] The vertices of a connected (finite) graph $G$ can always be enumerated, say as $v_1,\ldots,v_{|G|}$, so that $G_i := G[v_1,\ldots,v_i]$ is connected for every $i$. Now the coloring is done running through the enumeration provided by this proposition, via the greedy algorithm, and the removal of edges is done as stated above. Quite short and sweet.

This is most probably a silly question, but mavropnevma wrote: In our case we therefore have $m \geq \dfrac {n(n+1)} {2} = \dfrac {n(n-1)} {2} + n$, and at least we now know a graph with $\chi(G)\geq n+1$ has enough edges so we can remove $\dfrac{n(n-1)}{2}$ of them . On the other hand, we also have $\Delta(G) \geq n$. I understand how the bound of $|E| \geq \binom{\chi(G)}{2} = \binom{\chi(G)-1}{2} + \chi(G)-1$ is proved, and I also know that how the bound of $\Delta(G) \geq \chi(G) - 1$ is proved, but I don't see how putting them together leads the conclusion of the problem. Can somebody explain how it's relevant to the problem or how mavropnevma reaches to the conclusion in the bolded part ? I think using these two bounds, you can prove the weaker version that $|E| - \Delta(G) \geq \binom{\chi(G)-1}{2}$ but we need to prove the stronger version $|E|-|V|+1 \geq \binom{\chi(G)-1}{2}$ for the problem, right ?

The two bounds are not really relevant to the solution --- I guess they are just some of marvropnevma's initial thoughts. My understanding of the bolded part doesn't refer to being able to remove $\frac{n(n-1)}{2}$ edges from $G$ so that it remains connected but rather at the very least there is enough edges for it to be possible that $G$ is connected after removing that many edges (since a connected graph needs at least $n-1$ edges). If you read through his solution, there is a part where he claims "But clearly $\deg v \geq n$." This doesn't directly follow from $\Delta(G) \geq n$ but the proof is similar so that might be why he mentioned it.

redacted