The Feasibility Problem -- the family $\mathcal{F}$$(G)$ of all induced $G$-free graphs

Abstract

An infinite family of graphs $\mathcal{F}$ is called feasible if for any pair of integers $(n,m)$, $n\ge 1$, $0\le m\le \left(\genfrac{}{}{0ex}{}{n}{2}\right)$, there is a member $G\in \mathcal{F}$ such that $G$ has $n$ vertices and $m$ edges. We prove that given a graph $G$, the family $\mathcal{F}$$(G)$ of all induced $G$-free graphs is feasible if and only if $G$ is not $K_k$, $K_k\backslash K_2$, $\overline{K_k}$, $\overline{K_k\backslash K_2}$, for $k\ge 2$.