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?}


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: