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$ Feb 2, 2015 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, 2015 at 0:13
  • 2
    $\begingroup$ Oh wow, that was a terrible oversight - thanks so much! $\endgroup$
    – Christine
    Feb 2, 2015 at 0:14

1 Answer 1

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, 2020 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$ Dec 16, 2020 at 5:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .