1
$\begingroup$

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 : http://en.wikipedia.org/wiki/Complement_graph

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???

Thanks

  • 0
    Yeah now I see it, it makes a lot more sense. I guess I was a little desperate earlier.2012-11-23

2 Answers 2

4

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$).

  • 0
    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.2012-11-23
0

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)$.

  • 0
    @Zeelee You're welcome. I'm glad I could help.2012-11-23