## Problem1F

Problem1F: The girth of a graph is the length of the smallest polygon in the graph. Let ${G}$ be a graph with girth ${5}$ for which all vertices have degree ${\geq d}$. Show that ${G}$ has at least ${d^{2}+1}$ vertices. Can equality hold?

Solution: Fix a vertex ${v}$, since the girth is ${5}$, there is a unique path to a vertex of distance ${2}$ to ${v}$. The degree of ${v}$ is at least ${d,}$ so there are at least ${d}$ distinct vertices of distance ${1}$ to ${v. }$ Keep expanding the graph from these ${d}$ vertices, then we reach at least ${ d(d-1)}$ vertices of distance ${2}$ to ${v.}$ By the uniqueness of the path from ${v}$ to these vertices, the ${d(d-1)}$ vertices are all distinct. So there are at least ${1+d+d(d-1)=d^{2}+1}$ vertices in the graph. The equality can hold, a polygon of length ${5}$ is an example for ${d=2,}$ and the Petersen Graph is an example for ${d=3.}$

Note: Consider the general case: when the girth is even, we cannot find the exact lower bounds of the number of the vertices. When the girth is ${2n+1,}$ and degree of each vertex is ${\geq d,}$ what are the lower bounds of the number of vertices? Similarly, we derive the lower bound ${ =1+d\sum_{k=0}^{n-1}(d-1)^{k}.}$ Can equality hold for every ${n}$ and ${d?}$ The equlaity holds for every ${n}$ and ${d=2}$ trivially. What about for every ${n}$ and ${d=3?}$ I haven’t found a counter example that the equality cannot hold for ${d=3.}$ What about other ${d?}$