Question

PROBLEM 9. Find two nonisomorphic simple graphs that have six vertices and all vertices have degree degree 3.

Answer 1

Sr Scanned with CamScanner

Consider these two graphs, A and B. Note that both A and B are simple graphs with 6 vertices and each vertices have degree 3. Only to show these two graphs are non-isomorphic.

Recall a graph is bipartite if the set of graph vertices can be decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent.

To prove these two graphs are not isomorphic we will show the graph B is bipartite but A is not.

Note that for the graph B, {1,4,5} and {2,3,6} are two disjoint sets of vertices having no two adjacent vertices from each of the sets. Hence bipartite.

To prove A is not bipartite we will use a theorem of Konig , which states, a graph is bipartite if and only if it has no odd cycle. Note that the graph A consists a triangle, which is an odd cycle, hence A is not bipartite.

Feel free to put a comment if you have any doubts. Cheers!