Skip to main content
2 of 7
added 21 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This is a pretty interesting question. Here are some trivial observations. For an example of a connected non-bipartite graph that satisfies the property for $i=4$, we may take any odd cycle of length at least 5. On the other hand, large induced cycles force many induced subgraphs for all small values of $i$.

Lemma. Let $G$ be a graph with an induced cycle of length $g \geq 8$. If $G$ is not a cycle, then for all $4 \leq i \leq g/2$, the number of induced subgraphs of $G$ with $i$ vertices is more than $i$.

Proof. Let $C$ be an induced cycle of $G$ of length $g$. Let $F_i$ be the set of all forests on $i$ vertices with maximum degree 2. Observe that $C$ contains all graphs in $F_i$ for all $i \leq g/2$ as induced subgraphs. Note that $|F_i|>i$ for all $i>4$. This almost proves the lemma, except that $|F_4|=4$. But here we use the hypothesis that $G$ is not a cycle, in which case $G$ contains an induced subgraph $H$ on 4 vertices with maximum degree at least 3. Hence $H \notin F_4$ and we are done.

The property seems harder to satisfy for larger values of $i$ which leads us to the following rash conjecture.

Rash Conjecture. Let $G$ be a connected, non-bipartite graph on $n$ vertices whose complement is also connected and non-bipartite. If $G$ has at most $i$ induced $i$-subgraphs for some $3 < i < n/2$, then $G$ or its complement is an odd-cycle.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187