1
$\begingroup$

Find as many non-isomorphic self-complementary graphs as possible with up to $7$ vertices. State why there aren't more.

I've checked what a self-complementary graph is and wikipedia is saying: "A self-complementary graph is a graph which is isomorphic to its complement."

So then what is a non-isomorphic self-complementary graph? A graph which is non-isomorphic to its complement?

Here are some I found but I'm not sure if this is correct. All in all, this sounds very confusing, contradicting. Or did I just understand it wrong? How would you find more graphs?

enter image description here

Editing my question for Henning Makholm's answer:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ A graph can't be "non-isomorphic" by itself, just like a positive integer can't be "coprime" by itself. Perhaps it would be clearer if the question said "find as many self-complementary graphs as possible with up to 7 vertices, up to isomorphism". $\endgroup$ – NoName Nov 18 '17 at 23:25
2
$\begingroup$

Your two examples are only one example, since they are isomorphic.

It will help your search to notice that $K_6$ and $K_7$ both have an odd number of edges, so there is no self-complementary graph on $6$ or $7$ vertices. Having $2$ or $3$ vertices is taken care of by the same argument, and you have already found the single example (up to isomorphism) on $4$ vertices.

What is left for you is then only to enumerate graphs with $5$ vertices and $5$ edges, and check which of them are self-complementary.

$\endgroup$
  • $\begingroup$ I have just edited my question. Is that what you meant? $\endgroup$ – cnmesr Nov 18 '17 at 19:43
  • $\begingroup$ @cnmesr: Yes, that is one. There is at least one more with $5$ vertices, in addition to the trivial graph. $\endgroup$ – Henning Makholm Nov 18 '17 at 20:50
  • $\begingroup$ Thank you! Do you know what exactly is the reason there aren't more of these kind of graphs (with more than $7$ vertices)? $\endgroup$ – cnmesr Nov 18 '17 at 22:58
  • 1
    $\begingroup$ @cnmesr: Who says there aren't more? There are at least two with 8 vertices. $\endgroup$ – Henning Makholm Nov 18 '17 at 23:10

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.