0
$\begingroup$

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?

  • 3
    Can you add the definitions of $\delta(G)$, $\Delta(G)$ and $v(G)$?2011-08-02

1 Answers 1