Question

The distance between two distinct vertices\({{\bf{v}}_{\bf{1}}}\)and\({{\bf{v}}_{\bf{2}}}\)of a connected simple graph is the length (number of edges) of the shortest path between\({{\bf{v}}_{\bf{1}}}\)and\({{\bf{v}}_{\bf{2}}}\). The radius of a graph is the minimum over all vertices\({\bf{v}}\)of the maximum distance from\({\bf{v}}\)to another vertex. The diameter of a graph is the maximum distance between two distinct vertices. Find the radius and diameter of

a)\({{\bf{K}}_{\bf{6}}}\)

b)\({{\bf{K}}_{{\bf{4,5}}}}\)

c)\({{\bf{Q}}_{\bf{3}}}\)

d)\({{\bf{C}}_{\bf{6}}}\)

Short answer

(a) The diameter as well as radius is one in \({K_6}\).

(b) The diameter as well as radius is \(2\) in \({K_{4,5}}\).

(c) The diameter as well as radius is \(3\) in \({Q_3}\).

(d) The diameter as well as radius is \(3\) in \({C_6}\).

Step-by-step solution

Step 1:Given data

Given two vertices \({v_1}\)and \({v_2}\).

(a) Find \({{\bf{K}}_{\bf{6}}}\)

It has the maximum distance between any two vertices in \({K_6}\) is one, therefore the diameter is one.

Furthermore, taking any vertex as centre it has radius equals to one.

Hence, diameter as well as radius is one in \({K_6}\).

(b) Find \({{\bf{K}}_{{\bf{4,5}}}}\)

In the graph \({K_{4,5}}\) vertices in the same part are not adjacent, also no pair of vertices are at a distance greater than \(2\), so the diameter is \(2\).

Furthermore, taking any vertex as centre we have radius equals to \(2\).

Hence, diameter as well as radius is \(2\) in \({K_{4,5}}\).

(c) Find \({{\bf{Q}}_{\bf{3}}}\)

In the graph \({Q_3}\) the diameter is \(3\), since vertices at diagonally opposite corner of the cube are a distance \(3\) from each other.

Furthermore, taking any vertex as centre it has radius equals to\(3\).

Hence, diameter as well as radius is \(3\) in \({Q_3}\).

(d) Find \({{\bf{C}}_{\bf{6}}}\)

In the graph \({C_6}\) the diameter is \(3\), since vertices at opposite corners of the hexagon are a distance \(3\) from each other.

Furthermore, using symmetry into consideration,it can takes any vertex as centre so it has radius equals to \(3\).

Hence, diameter as well as radius is \(3\) in \({C_6}\).