Relation between complete graph $K_N$ and it's complete subgraph $K_n$

18 Views Asked by At

Suppose we have a complete graph $K_N$ with $\{1,\ldots,N\}$ vertices. Consider a complete subgraph $K_n\subseteq K_N$ from the original graph $K_N$.

Now I have a subgraph $A$ with $\{1,\ldots,k\}, k<n$ vertices. I want understand the following expression and how can we simplify this $$ W = \sum_{A\subseteq K_N} \mathbf{1} - \sum_{A\subseteq K_n}\mathbf{1} $$

I tried in this way \begin{align} W &= \sum_{A\subseteq K_N} \mathbf{1} - \sum_{A\subseteq K_n}\mathbf{1}\\ &= \sum_{A\subseteq K_N} \mathbf{1} - \sum_{A\subseteq K_N}w(n,N)\cdot\mathbf{1}\\ &= \sum_{A\subseteq K_N} (1-w(n,N))\cdot\mathbf{1} \end{align} Is there any expression available for $w(n,N)$? Any other way of simplification is appreciated.