4
$\begingroup$

Could someone verify this?

Pick a vertex $v$ of $G$. Pick distinct vertices $u_1, u_2, \ldots, u_d$ incident with $v$. Note that this can be done since $v$ has no loops and degree $\geq d$. For each $u_i$, pick distinct vertices $w_i^{(1)}, w_i^{(2)}, \ldots, w_i^{(d-1)}$ incident with $u_i$ other than $v$.

Then, $$w_i^{(k)} \neq w_j^{(l)}$$ To see this, note that $v, u_i, w_i^{(k)}, u_j, v$ would form a cycle of length $4$. Also, $$w_i^{(j)} \neq u_k$$ To see this, note that $v, u_k, u_i, v$ would form a cycle of length 3.

Also, $$v \neq w_i^{(j)}$$

Otherwise, $v, u_i, v$ would form a cycle of length $2$.

So, all of the edges $v, u_1, \ldots, u_d, w_1^{(1)}, \ldots, w_d^{(d-1)}$ are distinct. So, the graph contains at least $1+d+d(d-1) = 1+d^2$ vertices.$~~~~~~~~~$

$\endgroup$
1
  • 1
    $\begingroup$ You're right$~~$. $\endgroup$
    – pointer
    Commented Jun 15, 2014 at 16:07

1 Answer 1

6
$\begingroup$

It looks great! Another approach is the following:

Let $V$ be the set containing the vertex $u$ and it's neighbors. We see that $|V|\geq d+1$ since every vertex in $G$ has degree at least $d$. None of $u$'s neighbors are adjacent since $G$ has girth $5$. Consider $V-u$, every vertex in $V-u$ has degree at least $d-1$ and $|V-u|=d$. So $|\bar{V}|\geq d(d-1)=d^2-d$. Thus $G$ has at least $(d+1)+(d^2-d)=d^2+1$ vertices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .