Problem

Source: Iran TST 2015, exam 1, day 2 problem 2

Tags: combinatorics, graph theory



Let $A$ be a subset of the edges of an $n\times n $ table. Let $V(A)$ be the set of vertices from the table which are connected to at least on edge from $A$ and $j(A)$ be the number of the connected components of graph $G$ which it's vertices are the set $V(A)$ and it's edges are the set $A$. Prove that for every natural number $l$: $$\frac{l}{2}\leq min_{|A|\geq l}(|V(A)|-j(A)) \leq \frac{l}{2}+\sqrt{\frac{l}{2}}+1$$