For these exercises, assume all graphs are not the null graph. The \"girth\" of
ID: 3167490 • Letter: F
Question
For these exercises, assume all graphs are not the null graph. The "girth" of a graph G is the number of edges in a minimum-length cycle contained by G. The girth of an acyclic graph is oo, conventionally. Notice that if a graph is not simple, then its girth is either 1 or 2. Exercise 2.1.8 a) Show that a k - regular graph of girth 4 has at least 2k vertices. (Hint Consider neighbors of a given vertex.) Exercise 2.1.9 a) Show that a k - regular graph of girth 5 has at least k2 + 1 vertices. (Hint: Consider neighbors of neighbors.)Explanation / Answer
2.1.8 a)
Consider one vertex from the graph and it's k neighbors.
Thus we have k+1 vertices together.But these neighbors should not be connected because if they were connected,there would be a triangle.
If we take a glance at one of these neighbors which are not among the k+1 we tallied up until now.
Therefore,we have
total number of vertices=1+k+(k-1)=2k vertices
On the other hand, take two adjacent vertices.these vertices should not have common neighbors since otherwise there would be a triangle.Now, each of these two vertices has (k-1) new neighbors.
Thus,we have 2+2(k-1)=2k vertices.
2.1.9 a)
Consider any vertex v in V(G)
G is a quadrilateral-free graph.So,for any x,y N(V),x and y can't have a common neighbor other than v.
In this way,each of these k neighbors of v have k-1 different neighbors that doesn't have intersection amongst one another.
Altogether we have at least k(k-1)+k+1=k^2+1 vertices.