Combinatorial question regarding size of subsets of pairs

Question

Question: I have $l$ pairs $(x,y)$ with $x,y \in \{ 1,2,...,n \}$. How many different elements (in $ \{ 1,...n\}$) do we at least see among these pairs (depending on $l$)?

for example I tried to say if we have $k\cdot n$ many different elements that occur then we can form at most $(k \cdot n)^2$ couples with these elements. So we have to set $(k \cdot n)^2 \geq l$ and from there we get $k$ and finally the least number of different elements we need to form $l$ pairs. Does this make sense?

Answer 1

With $k$ pairwise different elements we can create $k^2$ different pairs.

If $l\geq 1$ pairs are given, the smallest number of different elements which are contained in $l$ pairs is the number

\begin{array}{lll} &k\qquad &\text{if } k^2=l&\\ &k+1\qquad &\text{if } k^2<l<(k+1)^2& \end{array}

which can be expressed compactly according to @BrianMScott's comment as $$\left\lceil\sqrt{l}\right\rceil$$

$\lceil x\rceil$ is denoting the ceiling function of $x$.