Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've spent a long time thinking by myself and I can't figure out how to proceed:

Is there a simple graph G with 60 edges such that it's complementary graph GC has 52 edges?

Also, on wikipedia I don't get this entry :

Formal construction

"Let G = (V, E) be a simple graph and let K consist of all 2-element subsets of V. Then H = (V, K \ E) is the complement of G."

Source :

What is K supposed to be? I don't get what are 2-element subsets of V. I've drawn a simple graph G(3,3) : triangle, which has a GC(3,k/3) : Three isolated vertices. So k should be equal to zero???


share|cite|improve this question
A 2-element subset of V is a subset of V containing precisely two elements. – Chris Eagle Nov 23 '12 at 19:16
Some of the things you say (and notation you use) look a bit strange to me. The first thing is that you use notation $G(3,3)$ and $G = (V, E)$ in the same text. The second is that you write $k/3$. It's almost as if you assumed that $V$, $K$ and $E$ are numbers and $\setminus$ is division, when in fact $V$, $K$ and $E$ are sets and $\setminus$ is set subtraction. At least that's how they are meant in that wikipedia article. – Dan Shved Nov 23 '12 at 19:26
Yeah now I see it, it makes a lot more sense. I guess I was a little desperate earlier. – Patrick.SE Nov 23 '12 at 19:33
up vote 4 down vote accepted

There is no such simple graph. Let n be the order of the graph. The sum $E(G)+E(G^-)=(n^2-n)/2$ . It turns out that $60+52=112=(n^2-n)/2$ has no integer solutions (because $(15^2-15)/2=105$, and $(16^2-16)/2=120$).

share|cite|improve this answer
I had that too, I did a ceiling of the integer to round it to the next integer thinking that it was possible if you had a V+1 graph then it would be possible. Your answer it great thanks. – Patrick.SE Nov 23 '12 at 19:35

Edges in a simple graph are often defined as $2$-element subsets of $V$, i.e. unordered pairs of vertices.

In this sense, $K$ is the set of all "potential edges" that can exist between vertices in $V$. $E \subset K$ is the set of those pairs of vertices that really are edges of $G$. And $K \setminus E$ are all the remaining pairs of vertices.

Imagine that you had a complete graph $ G_K = (V, K)$. Then you removed some edges from it to get $G = (V, E)$. And $K \setminus E$ is simply the set of all the edges that you have removed. Then of course $G^- = (V, K \setminus E)$ is the complementary graph of $G = (V, E)$.

share|cite|improve this answer
@Zeelee there was a bad typo in the answer. Fixed it. – Dan Shved Nov 23 '12 at 19:28
Thanks Dan, that has cleared up the second question. I don't know why I was seeing it with arithmetic instead of sets. – Patrick.SE Nov 23 '12 at 19:36
@Zeelee You're welcome. I'm glad I could help. – Dan Shved Nov 23 '12 at 19:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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