-4
$\begingroup$

given a graph G with a girth of 5, prove that for $delta(G)>=k$ (minimum degree), G has a least $k^2+1$ vertices.

Can anyone provide a hint or an approach for this?

Thanks

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Pick

  • a vertex,
  • its neighbours,
  • and their neighbours apart from the original vertex
$\endgroup$
1
  • $\begingroup$ thanks, that helped $\endgroup$
    – chendoy
    May 13, 2018 at 6:18

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