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

Consider any complete bipartite graph $K_{p,q}$. Express the number of edges in $K_{p,q}^C$, the complement of $K_{p,q}$, as a function of $n$, the total number of verticies.

Now, I know that I could do this by subtracting the number of edges in $K_{p,q}$ by the number of edges in $K_n$, a complete graph with $n$ vertices. However, I do not see how it is possible to determine the number of edges in $K_{p,q}$ merely as a function of $n$ because I need to know how many verticies are on each side of the graph in order to determine this. For instance, $K_{1,3}$ and $K_{2,2}$ both have 4 verticies, however, the former one has 3 edges whereas the latter has 4 edges because $$ The~number ~of ~edges ~in ~a ~complete ~bipartite ~graph~ K_{p,q} = pq$$

So I'm not sure that this can really be expressed solely as a function of $n$

share|cite|improve this question
Your reasoning is correct. $|E(K_{p,q}^C)|$ can't be expressed as a function solely of $n$. $|E(K_{p,q}^C)| = \binom{n}{2} - pq$, which varies depending on $p$ and $q$, since $pq$ can't be expressed in terms of $p+q$. – Perry Elliott-Iverson Mar 31 '14 at 17:33
up vote 1 down vote accepted

Edit: In light of $n = |V|$ rather than $n = |E|$. Here is my hint:

There are $\frac{p(p-1) + q(q-1)}{2}$ edges in the complement, right? Each vertex pair in set $P$ is adjacent, and each vertex pair in set $Q$ is adjacent. So we have $K_{p} \cup K_{q}$ as the complement.

I'd start there and do some algebra. I'd also consider that $q = n - p$ and see if that helps.

share|cite|improve this answer
how can $pq=n$? isn't $n= p+q$? – audiFanatic Mar 31 '14 at 16:04
Don't you define $n := |E(K_{p, q})| = pq$ in your original post? Look at the construction of $K_{p, q}$. Each vertex in $p$ has degree $q$. So there are $pq$ edges in $K_{p, q}$. – ml0105 Mar 31 '14 at 16:06
correct, I understand that, but $n$ is the total number of vertices, which is still $p+q$ – audiFanatic Mar 31 '14 at 16:11
You're throwing around $n$ to mean two different things. The variable $n$ is either the vertex count or the edge count of $K_{p, q}$. It is not both. Per your original post: "as a function of n, the total number of edges." – ml0105 Mar 31 '14 at 16:13
Turns out that the question was not worded correctly, I'll answer the question below how the professor intended it to be interpreted, but for all intents and purposes, you deserve the credit for helping me arrive at the conclusion and attempting to answer what was essentially a poorly worded question. – audiFanatic Mar 31 '14 at 20:38

So for those who are curious, the question was meant to be interpreted as follows.

Maximize the number of edges in the graph $G^C$ which has $n$ vertices.

We know that the number of edges in a complete graph, $K_n$ is $\frac{n(n-1)}{2}$ and the minimum number of edges in a connected graph of $n$ vertices is $n-1$. So that means that means $$ max\{|E_{G^C}|\} = \frac{n(n-1)}{2} - (n-1) $$ $$ s.t. n=p+q$$

Doing some algebra, we can arrive at $$ max\{|E_{G^C}|\} = \frac{(n-1)(n-2)}{2} $$ and this occurs when $p = 1$ and $ q = n-1$ or vice-versa

share|cite|improve this answer
Actually, the minimum number of edges in a graph on $n$ vertices (note spelling: vertices, not verticies) is $0$. Was the question supposed to be about a connected graph? By the way, what is the relevance of the fact that the graph is bipartite? – bof Mar 31 '14 at 21:19
Ah yes, I wrote the answer assuming connectedness – audiFanatic Apr 1 '14 at 15:24

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.