6 edited body

Here's an example $G$ for all $i \geq 8$ and $n \geq 2i+1$ that contains only $6$ 8$induced subgraphs (up to isomorphism). If we choose$i$vertices from the top row, we obtain$\overline{K_i}$. If we choose$i-1$vertices from the top row, we obtain$K_{1,i-1}$or$\overline{K_i}$. If we choose$i-2$vertices from the top row, we obtain$\overline{K_i}$or$\overline{K_{i-2}} \cup K_2$or$K_{1,i-2} \cup K_1$or$K_{1,i-1}$. If we choose$i-3$vertices from the top row, we obtain the subgraphs induced by$i-3 \text{ vertices from a,b,c,d,... } \cup {e,g,h}$or$i-3 \text{ vertices from a,b,c,d,... } \cup {e,f,g}$or$K_{1,i-2} \cup K_1$or$\overline{K_{i-3}} \cup P_3$(path with three vertices). If we choose$i-4$vertices from the top row, we obtain the graph induced by$i-4 \text{ vertices from a,b,c,d,... } \cup {e,f,g,h}$. Since we must choose at least$i-4$vertices from the top row, in total, that's 8 isomorphism classes of graphs. We can see that$G$and its complement both contain a triangle (and are therefore not bipartite) and are connected (each vertex is not adjacent to either h or a). Generalising this technique, we can replace {e,f,g,h} by any non-bipartite connected subgraph of diameter at least 2. In this case, there would exist some I, N such that for all i>=I and n>=max(N,2i+1) which would satisfy the required conditions. 5 added 60 characters in body; added 27 characters in body; added 11 characters in body; deleted 11 characters in body Here's an example$G$for all$i \geq 8$and$n \geq 2i+1$that contains only$6$induced subgraphs (up to isomorphism). If we choose$i$vertices from the top row, we obtain$\overline{K_i}$. If we choose$i-1$vertices from the top row, we obtain$K_{1,i-1}$or$\overline{K_i}$. If we choose$i-2$vertices from the top row, we obtain$\overline{K_i}$or$\overline{K_{i-2}} \cup K_2$or$K_{1,i-2} \cup K_1$or$K_{1,i-1}$. If we choose$i-3$vertices from the top row, we obtain the subgraphs induced by$i-3 \text{ vertices from a,b,c,d,... } \cup {e,g,h}$or$i-3 \text{ vertices from a,b,c,d,... } \cup {e,f,g}$or$K_{1,i-2} \cup K_1$or$\overline{K_{i-3}} \cup P_3$(path with three vertices). If we choose$i-4$vertices from the top row, we obtain the graph induced by$G \setminus i-4 \text{ vertices from a,b,c,d,... } $.\cup {e,f,g,h}$.

Since we must choose at least $i-4$ vertices from the top row, in total, that's 8 isomorphism classes of graphs. We can see that $G$ and its complement both contain a triangle (and are therefore not bipartite) and are connected (each vertex is not adjacent to either h or a).

Generalising this technique, we can replace {e,f,g,h} by any non-bipartite connected subgraph of diameter at least 2. In this case, there would exist some I, N such that for all i>=I and n>=max(N,2i+1) which would satisfy the required conditions.

4 error in previous version; added 7 characters in body; added 14 characters in body; deleted 1 characters in body

Here's an example $G$ for all $i \geq 4$ 8$and$n \geq 2i+1$that contains only$4$6$ induced subgraphs (up to isomorphism).

If we choose $i$ vertices from the top row, we obtain $\overline{K_i}$.

If we choose $i-1$ vertices from the top row, we obtain $K_{1,i-1}$ or $\overline{K_i}$.

If we choose $i-2$ vertices from the top row, we obtain $K_2 \overline{K_i}$ or $\overline{K_{i-2}} \cup K_2$ or $K_{1,i-2} \overbrace{K_1 cup K_1$ or $K_{1,i-1}$.

If we choose $i-3$ vertices from the top row, we obtain the subgraphs induced by $i-3 \text{ vertices from a,b,c,d,... } \cup {e,g,h}$ or $i-3 \cdots text{ vertices from a,b,c,d,... } \cup K_1}^{i-2}$ {e,f,g}$or$K_{1,i-1}$.K_{1,i-2} \cup K_1$.

If we choose $i-3$ i-4$vertices from the top row, we obtain$G \setminus {a,b,c}$.i-4 \text{ vertices from a,b,c,d,... }$.

Since we must choose at least $i-3$ i-4$vertices from the top row, in total, that's four 8 isomorphism classes of graphs. We can easily see that$G\$ and its complement both contain a triangle (and are therefore not bipartite) and are connected (each vertex is not adjacent to either h or a).

Generalising this technique, we can replace {e,f,g,h} by any non-bipartite connected subgraph of diameter at least 2. In this case, there would exist some I, N such that for all i>=I and n>=max(N,2i+1) which would satisfy the required conditions.

3 generalised the example
2 edited body
1