show/hide this revision's text 7 deleted 79 characters in body

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 provides an example that works (but has diameter 3). 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.

show/hide this revision's text 6 deleted 239 characters in body

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 9see 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$. If $G$ has a vertex of degree at least 3, then 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. Note that Since $|F_i|>i$ F_i > i$ for all $i>4$. This almost proves the lemma, except that $|F_4|=4$. But since $G$ contains a vertex of degree at least 3i \geq 4$, it must contain an induced subgraph $H$ that is not in $F_4$, and so 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$ or its complement is an odd-cyclehas diameter at most 7.

show/hide this revision's text 5 deleted 37 characters in body

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 9. 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$. If $G$ is not has a cyclevertex of degree at least 3, 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. 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 since $G$ is not contains a cyclevertex of degree at least 3, in which case $G$ contains it must contain an induced subgraph $H$ on 4 vertices with maximum degree at least 3. Hence that is not in $H \notin F_4$ F_4$, and so 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.

show/hide this revision's text 4 deleted 20 characters in body
show/hide this revision's text 3 edited body
show/hide this revision's text 2 added 21 characters in body
show/hide this revision's text 1