1
$\begingroup$

I am trying to solve the following problem:

Let $G$ be a graph on $n$ vertices. Assume $G$ is disconnected such that any connected component has size $\geq K$. Show that $|E(G)| \leq \binom{k}{2} + \binom{n-k}{2}$.

The first term is kind of obvious. Every $k$-size connected component could be at most a clique and a clique has $\binom{k}{2}$ edges. That would leave us with $n-k$ vertices in the components that can be connected between them (only in the components though). How can we prove that this number is $\binom{n-k}{2}$? I thought about splitting this term into $n_1, n_2, \dots, n_m$ vertices for the $m$ connected components such that their sum is $n-k$ and then use properties of the binomial coefficients but I couldn't prove an equality between the second terms.

Any hints/ideas about that or another direction?

$\endgroup$
  • $\begingroup$ The bound looks like something that would come up from splitting the graph in two sets one with $k$ vertices and one with $n-k$ and bounding the number of edges on each set. $\endgroup$ – Quimey Aug 21 '18 at 19:46
1
$\begingroup$

A connected component of $m$ vertices contains at most $\binom{m}{2}$ edges, and there at most $\binom{n-m}{2}$ edges outside it. Hence $|E(G)|\leq\binom{m}{2}+\binom{n-m}{2}$. Because $n>m\geq k$ it follows that $$\binom{m}{2}+\binom{n-m}{2}=\frac{1}{2}(n^2+(2m-2n+1)m)\leq\frac{1}{2}(n^2+(2k-2n+1)k)=\binom{k}{2}+\binom{n-k}{2}.$$

$\endgroup$
  • $\begingroup$ Damn I was close.. Thanks! $\endgroup$ – koygian Aug 21 '18 at 19:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.