Question

Find the two non-isomorphic simple graphs with six vertices and nine edges that have optimal connectivity.

Short answer

The \({K_{3,3}}\) and skeleton of a triangular prism graph are the only non-isomorphic simple graphs with six vertices and nine edges that have optimal connectivity.

Step-by-step solution

Concept/Significance of connected graph

A connected graph is one in which all of the vertices are linked together. It is not necessary for all vertices to be linked to one another.

Determination of non-isomorphic simple graphs with six vertices and nine edges that have optimal connectivity 

The graph\({K_{3,3}}\)is one of the graphs which has 6 vertices, 9 edges, and each vertex of degree 3 and it is non-isomorphic simple graph.

And, the skeleton of a triangular prism turns out to be the only other graph with this feature.

Thus, \({K_{3,3}}\) and skeleton of a triangular prism graph are the only non-isomorphic simple graphs with six vertices and nine edges that have optimal connectivity.