Return to Answer

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.

This is a pretty interesting question. 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.

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$ has a vertex 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 since $G$ contains a vertex of degree at least 3, 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 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.

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.

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 a cycle, 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 $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.

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$ has a vertex 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 since $G$ contains a vertex of degree at least 3, 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 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.