5 points each The diameter of a graph is the longest distanc

(5 points each) The diameter of a graph is the longest distance between two points on a graph. We say the diameter is infinite if the graph is not connected. The girth of a graph is the shortest length cycle in a graph. We say the girth is infinite if the graph is acyclic. Find the diameter d and girth g of the following graphs: (a) The complete graph K5 (b) The complete bipartite graph K3,2 (c) The Petersen Graph

Solution

In a graph theory the girth of a graph is the length of the shortest cycle contained in the graph.

For example a four cycle (square) has a girth 4.

A graph with triangle shape has girth 3 and all other graphs which are triangle free have girth 4 or more.

The Petersen graph has a girth 5 and it has diameter 2.

You can see that the maximum distance from one vertex of petersen graph to other vertex is 2. So we got the diameter as 2.

We can do the same thing to find the diameter of K2,3 and K5.

For girth find the shortest cycle contained in graph of k5 and k2,3.

Hope this will help you.

Thanks.