I have the following problem: Let $G$ be a graph with the girth of $G$ at least 4. Show that $v(G)\geq\delta(G)+\Delta(G)$. My proof involves the use of $\delta(G)$, but I am not too sure of the role that $\Delta(G)$ plays in this problem. Can anyone give me a hint on that?
Girth and maximal and minimal degrees
0
$\begingroup$
graph-theory
-
3Can you add the definitions of $\delta(G)$, $\Delta(G)$ and $v(G)$? – 2011-08-02