2
$\begingroup$

I am having some trouble seeing why a graph of 4 nodes and 2 edges is not self-complementary such that $G$ is isomorphic to $\overline{G}$ (G complement) (please see the attachment below). I know that the number of edges in a self-complementary graph must be $\frac{1}{4}n(n-1)$, (half of that of a $K_n$ graph) and so for a graph of 4 nodes, the number of edges must be 3. However, why is the graph attached not self-complementary?

enter image description here

The number of edges, nodes, the degree sequence, length of cycles, etc., are the same, and could I not map $G$ and $G$ complement like: $f(d) = b$; $f(b) = d$; $f(a) = a$; $f(c) = c$?

I must be missing something about isomorphism here - if someone could point it out, that'd be great - thanks so much!

$\endgroup$
3
  • $\begingroup$ You’re missing the fact that $\overline G$ also has the edges $ac$ and $bd$. $\endgroup$ – Brian M. Scott Feb 2 '15 at 0:12
  • $\begingroup$ I don't think you are missing something about isomorphism, I think you are missing something about complement. Your second graph is not the complement of your first. $\endgroup$ – David Feb 2 '15 at 0:13
  • 2
    $\begingroup$ Oh wow, that was a terrible oversight - thanks so much! $\endgroup$ – Christine Feb 2 '15 at 0:14
2
$\begingroup$

As David pointed out in a comment, the second graph is simply not the complement of the first.

$\endgroup$
2
  • $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review $\endgroup$ – Anonymous Dec 16 '20 at 4:57
  • 1
    $\begingroup$ @Anonymous The question's already been answered in the comments, so the only reason I posted this answer was to remove this question from the "unanswered" queue. Maybe be a little more careful in your judgements in the review queues in the future. $\endgroup$ – Robert Howard Dec 16 '20 at 5:13

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.