Is every graph on n ≥ 1 vertices isomorphic to infinitely many graphs?

603 Views Asked by At

I know this that every graph is isomorphic to itself so there is always one graph that is isomorphic to it but for infinitely many it seems incorrect. Also if it is possible can someone give a hint on the proof. Thanks.

Question-"Is every graph on n ≥ 1 vertices isomorphic to infinitely many graphs?"

1

There are 1 best solutions below

0
On

In some sense, yes, each non-empty graph is isomorphic to infinitely many other graphs (and that infinity is as big as infinities can get). The reason is that we aren't told what the vertices are. So the graph with the only vertex being the natural number $1$ is isomorphic to the graph with the only vertex being the set of complex numbers, but they are unequal as their set of vertices aren't equal. And you can probably imagine how it goes on from there.

Usually, we don't care about what the vertices really are when we do graph theory, though. Just as linear algebra doesn't care what vectors really are, and geometry doesn't care what points really are. So people may get a little vague on the distinction between equality and isomorphism between graphs.