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
1 Answers
1
I’m going to assume that $v(G)$ is the number of vertices of $G$, $\delta(G)$ is the minimum degree of any vertex of $G$, and $\Delta(G)$ is the maximum degree of any vertex of $G$. Let $v_0$ be a vertex of degree $\Delta(G)$, and let $v_1,v_2,\dots,v_{\Delta(G)}$ be the vertices adjacent to $v_0$. Now consider $v_1$; it must be adjacent to at least $\delta(G)$ vertices. One of these is $v_0$; let the others be $w_1,w_2,\dots,w_{\delta(G)-1}$. Can any two of the vertices in the set $\{v_0,v_1,\dots,v_{\Delta(G)},w_1,\dots,w_{\delta(G)-1}\}$ be the same? Remember, a graph with girth at least $4$ contains no triangles.