Assume that a simple graph has $2n$ vertices and the property that every subset of $n$ vertices induces a subgraph with at least $k$ edges.

Question: What lower bounds are known on the total number of edges?

For example, if $k=n$, then the graph should have at least $5n$ edges.

We can see this by splitting the set of vertices into two disjoint sets $V_1,V_2$ such that $V_2$ induces a subgraph with minimum number of edges. Denote by $d_2(v)$ the number of edges of $v$ connecting it to a vertex of $V_2$.

If $v_1\in V_1$ and $v_2\in V_2$ we have that $d_2(v_1)\geq d_2(v_2)$, otherwise we can make $v_1,v_2$ switch subsets and make $V_2$ have less edges.

Assume that there is $v_1\in V_1$ with $d_2(v_1)\leq 2$. Then all $v_2\in V_2$ will have $d_2(v_2)\leq 2$. This gives at most $n$ edges in the graph induced by $V_2$ with equality only if $d_2(v_2)=2$ for all $v_2\in V_2$. Therefore, if $d_2(v_1)\leq2$ we must have $d_2(v_1)=2$ and $d_2(v_2)=2$ for all $v_2\in V_2$. But then switching $v_1$ and one of its $V_2$ adjacent vertices we degrease the number of edges in the graph induced by $V_2$.

Therefore, $d_2(v_1)\geq 3$ for all $v_1\in V_1$. This implies that we must have $n$ edges in the graph induced by $V_1$, also $n$ edges in the graph induced by $V_2$ and at least $3n$ edges going from vertices in $V_1$ to vertices in $V_2$. In total $5n$ edges.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.