A maximum problem in graph

66 Views Asked by At

Suppose that there is a graph with $x$ points and $y$ edges. $y$ is lower that ${x \choose 2}$ and between any two points there is at most one edge. These edges are distributed almost uniformly over all $x$ points and so the degree of them are almost the same. Then we split the $x$ points into two subsets $A$ and $B$ with cardinality $a$ and $b$, respectively, where $a+b=x$. We call the edges that connect two points in a single subset, an inner edge, and edges that connect two points each in a distinct subset, a cross edge. Now, what is the maximum possible number of inner edges in terms of $a, b, x$ and $y$ for subset $A$ and $B$?
e.g.: Here $$\mbox{inner edge}_A+\mbox{inner edge}_B+\mbox{cross edge}_{A,B}=y.$$