# number of edges in the complement of a complete bipartite graph as a function of $n$, the toal number of verticies

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$

• 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

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.

• 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

• 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