Question

Show that a connected graph with optimal connectivity must be regular.

Short answer

It is shown that all of the vertices in a connected graph have the same degree; so a linked graph with optimal connectivity must be regular.

Step-by-step solution

Concept/Significance of connectedness of a graph

A graph is considered to be linked if every pair of vertex has a route connecting them. There should be a route connecting every vertex to every other vertex. This is referred to as a graph's connectedness.

Showing thata connected graph with optimal connectivity must be regular

Consider the linked graph Gwhere m and n are the number of edges and vertices, respectively.The average vertex degree is,\(\frac{{2m}}{n}\)(according to the Handshaking theorem).

However, under the specified constraints, this is equivalent to the vertex's minimal degree.

As a result, for an average vertex to equal the term with the lowest value, all of the vertices must have the same value.

Thus, all of the vertices have the same degree; so a linked graph with optimal connectivity must be regular.