I'm trying to solve this problem in graph theory:
Prove that for every graph $G = (V, E)$ with $E \neq \varnothing $, it is true that: $$\Delta (G) \geq \left \lceil \frac{\left | E \right |}{\min\left \{\frac{\left | V \right |}{2} , \tau (G)\right\}} \right \rceil$$ where $\Delta (G)$ indicates graph's maximum degree, and $\tau (G)$ is the vertex number, i.e, the minimum number of vertex needed to cover all edges of the graph.
but I can't really think of any solution.
Thanks!
It suffices to show $\Delta(G) \ge 2|E|/|V|$ and $\Delta(G) \ge |E|/\tau(G)$. The first inequality is a consequence of the handshake lemma. For the second, consider a set of $\tau(G)$ vertices that covers all edges of the graph, and consider the sum of the degrees of these vertices.