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

Question

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$

Answer 1

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.

Answer 2

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