**Problem1F: The girth of a graph is the length of the smallest polygon in the graph. Let **** be a graph with girth **** for which all vertices have degree ****. Show that **** has at least **** vertices. Can equality hold?**

**Solution: **Fix a vertex , since the girth is , there is a unique path to a vertex of distance to . The degree of is at least so there are at least distinct vertices of distance to Keep expanding the graph from these vertices, then we reach at least vertices of distance to By the uniqueness of the path from to these vertices, the vertices are all distinct. So there are at least vertices in the graph. The equality can hold, a polygon of length is an example for and the Petersen Graph is an example for

**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 and degree of each vertex is what are the lower bounds of the number of vertices? Similarly, we derive the lower bound Can equality hold for every and The equlaity holds for every and trivially. What about for every and I haven’t found a counter example that the equality cannot hold for What about other