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
    A 2-element subset of V is a subset of V containing precisely two elements.2012-11-23
  • 0
    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.2012-11-23
  • 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 there was a bad typo in the answer. Fixed it.2012-11-23
  • 0
    Thanks Dan, that has cleared up the second question. I don't know why I was seeing it with arithmetic instead of sets.2012-11-23
  • 0
    @Zeelee You're welcome. I'm glad I could help.2012-11-23