I'm new to graph theory and was wondering:

Can two graphs with every vertex's order being more than 2 and have the same number of vertices and edges be non-isomorphic?


Yeah it's possible. For example take $n=6$ and each of the vertices have degree $3$. Then you can construct $K_{3,3}$ the complete bipartite graph on $6$ vertices and also another graph which isn't bipartite. The second graph can be obtained by constructing two distinct $C_3$ cycles and then connecting three pairs of vertices from distinct cycles. As both don't share a property (namely bipartivity) then they can't be isomorphic to each other.

You can find a picture of the two non-isomoprhic graphs here.

  • 1
    $\begingroup$ That other graph could be visualised as the edges of a triangular prism. $\endgroup$ – Jaap Scherphuis Nov 22 '17 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.