Skip to main content
6 of 7
deleted 239 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$, see Douglas S. Stones' answer. On the other hand, large diameter forces many induced subgraphs for all small values of $i$.

Lemma. Let $G$ be a graph with diameter $d \geq 8$. Then for all $4 \leq i \leq d/2$, the number of induced subgraphs of $G$ with $i$ vertices is more than $i$.

Proof. Let $P$ be an induced path of $G$ with $d$ vertices. Let $F_i$ be the set of all forests on $i$ vertices with maximum degree 2. Observe that $P$ contains all graphs in $F_i$ for all $i \leq d/2$ as induced subgraphs. Since $F_i > i$ for all $i \geq 4$, we are done.

The property seems harder to satisfy for larger values of $i$ which leads us to the following (updated) 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$ has diameter at most 7.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187