# The minimum number of maximal independent sets in twin-free graphs

Stijn Cambie Extremal Combinatorics and Probability Group (ECOPRO), Institute
for Basic Science (IBS), Daejeon, South Korea, supported by the Institute for
Basic Science (IBS-R029-C4), E-mail<EMAIL_ADDRESS>Stephan Wagner
Department of Mathematics, Uppsala University, Uppsala, Sweden, supported by
the Knut and Alice Wallenberg Foundation (KAW 2017.0112), E-mail:
<EMAIL_ADDRESS>
###### Abstract

The problem of determining the maximum number of maximal independent sets in
certain graph classes dates back to a paper of Miller and Muller and a
question of Erdős and Moser from the 1960s. The minimum was always considered
to be less interesting due to simple examples such as stars. In this paper we
show that the problem becomes interesting when restricted to twin-free graphs,
where no two vertices have the same open neighbourhood. We consider the
question for arbitrary graphs, bipartite graphs and trees. The minimum number
of maximal independent sets turns out to be logarithmic in the number of
vertices for arbitrary graphs, linear for bipartite graphs and exponential for
trees. In the latter case, the minimum and the extremal graphs have been
determined earlier by Taletskiĭ and Malyshev, but we present a shorter proof.

##  1 Introduction

###  1.1 History on the maximum number of maximal independent sets

Let $i_{\text{max}}(G)$ denote the number of maximal independent sets of a
graph $G$, i.e., the number of independent sets that are not contained in any
larger independent set. Answering a question on the number of (maximal)
cliques posed by Erdős and Moser, Moon and Moser [16], independently from
Miller and Muller [15] (see also [21] for a short alternative proof) proved
(by considering the complement) that for a graph $G$ of order $n$, where
$n\geq 2$,

$i_{\text{max}}(G)\leq\begin{cases}3^{\frac{n}{3}}&\text{ if }n\equiv
0\pmod{3},\\\ 4\cdot 3^{\frac{n-4}{3}}&\text{ if }n\equiv 1\pmod{3},\\\ 2\cdot
3^{\frac{n-2}{3}}&\text{ if }n\equiv 2\pmod{3}.\\\ \end{cases}$

The extremal graphs are disjoint unions of (at most two) $K_{2}$s and many
$K_{3}$s. In the original setting (for the number of maximal cliques), the
extremal graph is a balanced
$\mathopen{}\left\lceil\frac{n}{3}\right\rceil\mathclose{}-$partite graph.
Wilf [20] proved that among all trees of order $n$ the spiders (presented in
Figure 1) maximize the number of maximal independent sets. For a tree $T$ with
$n$ vertices,

$i_{\text{max}}(T)\leq\begin{cases}2^{\frac{n}{2}-1}+1&\text{ if }n\equiv
0\pmod{2},\\\ 2^{\frac{n-1}{2}}&\text{ if }n\equiv 1\pmod{2}.\\\ \end{cases}$

(a) An odd spider

(b) An even spider

Figure 1: Two spiders.

By induction, one can verify with Wilf’s idea that the extremal tree is unique
when $n$ is odd, but this is not the case when $n$ is even. Sagan [18]
provided an alternative proof for Wilf’s result and also characterized the
extremal trees of even order as batons of length $1$ or $3$. Here batons are
subdivisions of trees of diameter at most $3$ in which the pendent edges are
subdivided once and the central edge (or one edge of a star) is not subdivided
or subdivided twice. Examples of such batons are presented in Figure 2. From
this one can also conclude that there are precisely $\frac{n}{2}-1$ extremal
trees if $n\geq 4$ is even.

(a) A baton of length $1$

(b) A baton of length $3$

Figure 2: Batons of length $1$ and $3$.

Wilf also asked about the maximum of $i_{\text{max}}(G)$ when considering
arbitrary connected graphs of given order. This question was answered
independently by Füredi [6] (for large $n$) and Griggs et al. [7]. They proved
that for a connected graph $G$,

$i_{\text{max}}(G)\leq\begin{cases}2\cdot
3^{\frac{n}{3}-1}+2^{\frac{n}{3}-1}&\text{ if }n\equiv 0\pmod{3},\\\
3^{\frac{n-1}{3}}+2^{\frac{n-4}{3}}&\text{ if }n\equiv 1\pmod{3},\\\ 4\cdot
3^{\frac{n-5}{3}}+3\cdot 2^{\frac{n-8}{3}}&\text{ if }n\equiv 2\pmod{3}.\\\
\end{cases}$

For $n\geq 6$, the extremal graph is unique: if $n\equiv k\pmod{3}$, where
$k\in\\{0,1,2\\}$, the graph is obtained from a union of $k$ complete graphs
$K_{4}$ and
$\frac{n-4k}{3}=\mathopen{}\left\lfloor\frac{n}{3}\right\rfloor\mathclose{}-k$
complete graphs $K_{3}$ by choosing one vertex from each of these complete
graphs and connecting them to form a star of order
$\mathopen{}\left\lfloor\frac{n}{3}\right\rfloor\mathclose{}$. The centre of
this star has to belong to a $K_{4}$, if there is one. This is presented in
Figure 3 in the case $n\equiv 2\pmod{3}$.

$\cdots$
Figure 3: Connected graph with maximum value of $i_{\text{max}}$.

###  1.2 The minimum number of maximal independent sets

Whenever a graph contains at least one edge, we must clearly have
$i_{\text{max}}(G)\geq 2$ (construct maximal independent sets greedily
starting from each of the ends of one edge), and this bound is in fact
attained by a star. As such, one can conclude that for trees or arbitrary
connected graphs of order $n$, the best lower bound one can aim for is
$i_{\text{max}}(G)\geq 2$.

If two leaves $v,v^{\prime}$ of a tree have the same neighbour (we call such
leaves _twins_), then $v$ belongs to a maximal independent set if and only if
$v^{\prime}$ does, so we can consider them as essentially being one vertex.
Generally, if two vertices $v$ and $v^{\prime}$ of a graph have the same open
neighbourhood, i.e., $N(v)=N(v^{\prime})$, then every maximal independent set
either contains both or neither.

So by duplicating vertices (adding new vertices with the same open
neighbourhood as existing vertices), we can construct infinitely many graphs
with the same number of maximal independent sets. This is also the reason why
the question for the minimum number of maximal independent sets appears to be
less interesting than its counterpart for the maximum. As we will see, it
becomes more interesting if we forbid duplicated vertices:

######  Definition 1.

A graph is called _twin-free_ if it has no two vertices with the same
neighbours.

Twin-free graphs have been studied in the past, e.g. in [4] in connection with
identifying codes. Note that every graph can be reduced to a twin-free graph
(its “twin-free core”) by removal of duplicates without affecting the number
of maximal independent sets. We therefore study the problem of determining the
minimum of $i_{\text{max}}(G)$ for a twin-free graph $G$ of given order $n$ in
different graph classes: specifically, arbitrary graphs, bipartite graphs, and
trees.

We will see that for these three graph classes, the minimum of
$i_{\text{max}}(G)$ is logarithmic, linear and exponential in terms of the
order $n$, respectively.

Our first main result determines the minimum of $i_{\text{max}}(G)$ for
arbitrary connected twin-free graphs of given order, and characterizes the
extremal graph uniquely. We first prove that the extremal graph contains a
clique of order $i_{\text{max}}(G)$, and that the neighbourhoods satisfy
certain conditions. Using a result from extremal set theory, we can then
conclude with the following theorem. This is presented in Section 2.

######  Theorem 2.

Let $k\geq 2$ be an integer. If $G$ is a connected twin-free graph with $n$
vertices and $i_{\text{max}}(G)=k$, then $n\leq 2^{k-1}+k-2$. Furthermore,
equality holds only if the graph $G$ is formed by taking a clique $K_{k-1}$
and adding, for every non-empty vertex subset $S$ of this clique, a vertex
whose neighbourhood is precisely $S$.

The precise result for bipartite graphs is stated in the next theorem. In the
proof in Section 3, we associate a unique maximal independent set to every
vertex $v$ in one partition class, which together with the other partition
class gives the lower bound on the number of maximal independent sets.

######  Theorem 3.

Let $G$ be a connected twin-free bipartite graph of order $n\geq 2$. Then
$i_{\text{max}}(G)\geq\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}+1$,
and this inequality is sharp.

The last result determines the minimum number of maximal independent sets in
twin-free trees. This was previously proven by Taletskiĭ and Malyshev in [19].
We give a shorter proof in Section 4, which starts by deriving the bounds, in
contrast to [19] where the extremal graphs are characterized first by
excluding certain structures in the extremal graphs. We use an inductive
approach, based on a lemma of Wilf [20].

######  Theorem 4.

Let $n\geq 4$ be an integer. Then for every twin-free tree $T$ with $n$
vertices, we have

$i_{\text{max}}(T)\geq\begin{cases}4\cdot 3^{\frac{n}{5}-1}&\text{ if }n\equiv
0\pmod{5},\\\ 5\cdot 3^{\frac{n-6}{5}}&\text{ if }n\equiv 1\pmod{5},\\\ 2\cdot
3^{\frac{n-2}{5}}&\text{ if }n\equiv 2\pmod{5},\\\ 8\cdot
3^{\frac{n-8}{5}}&\text{ if }n\equiv 3\pmod{5},\\\ 3^{\frac{n+1}{5}}&\text{ if
}n\equiv 4\pmod{5},\end{cases}$

and this inequality is sharp.

For every $n$, Figure 4 depicts one example of a tree for which equality holds
in Theorem 4. Here, the blue and red edges possibly have to be added depending
on $n\pmod{5}$. For large $n$, there are multiple extremal trees. In
Subsection 4.1 we briefly make some comments on the characterization, which
also already appears in [19].

$\mathopen{}\left\lfloor\frac{n-4}{5}\right\rfloor\mathclose{}$ times (a)
$n\equiv 0,1,4\pmod{5}$

$\mathopen{}\left\lfloor\frac{n-7}{5}\right\rfloor\mathclose{}$ times (b)
$n\equiv 2,3\pmod{5}$

Figure 4: Constructions that attain equality in Theorem 4.

Finally, in Section 5, we conclude with some further directions related to the
minimum of $i_{\text{max}}(G)$ for twin-free graphs in other classes and some
other related questions.

##  2 Twin-free graphs

We start with the proof that the minimum of the number of maximal independent
sets in a connected twin-free graph is logarithmic in the order. We first
provide the extremal construction and give a short argument for the lower
bound $i_{\text{max}}(G)>\log_{2}(n)$. The more precise Theorem 2 is proven
afterwards in Subsection 2.1.

######  Proposition 5.

There exists a connected twin-free graph with $n=2^{k-1}+k-2$ vertices for
which $i_{\text{max}}(G)=k$.

###### Proof.

Let $K_{k-1}$ be a clique on $k-1$ vertices. For every non-empty vertex subset
$S$ of this clique, we add a new vertex whose neighbours are exactly the
vertices in $S$. Then the graph $G$ obtained by this process has
$k-1+(2^{k-1}-1)$ vertices, and all neighbourhoods are different, i.e., $G$ is
twin-free. Every independent set contains at most one vertex of the clique
$K_{k-1}$. We note that a maximal independent set $I$ is uniquely determined
by $I\cap V(K_{k-1})$, since $V(G)\setminus V(K_{k-1})$ is an independent set.
If $I\cap V(K_{k-1})=\emptyset$, then $V(G)\setminus V(K_{k-1})$ becomes a
maximal independent set on its own. If $I\cap V(K_{k-1})=\\{v\\}$, then
$I=V\backslash N(v).$ As such, we conclude that $i_{\text{max}}(G)=k$. ∎

Figure 5: The construction in Proposition 5 for $k=4$. The clique $K_{3}$ is
indicated in blue.

On the other hand, we can prove a lower bound that is based on the following
observation.

######  Lemma 6.

Two vertices $u$ and $v$ belong to the same maximal independent sets of a
graph $G$ if and only if they are twins.

###### Proof.

If $u$ and $v$ belong to the same maximal independent sets, then they cannot
be neighbours, and they must have exactly the same neighbours: if for instance
there was a vertex $w$ adjacent to $u$, but not to $v$, then there would be a
maximal independent set containing $\\{v,w\\}$, but not $u$. Hence $u$ and $v$
have to be twins. The converse is immediate. ∎

The following proposition already shows that the minimum of $i_{\text{max}}$
is of logarithmic order.

######  Proposition 7.

For every connected twin-free graph $G$ with $n$ vertices,
$i_{\text{max}}(G)>\log_{2}(n).$

###### Proof.

Let $k=i_{\text{max}}(G)$, and let the maximal independent sets of $G$ be
$I_{1},\ldots,I_{k}$. For every vertex $v$, consider the associated vector
$\vec{v}=\left(1_{v\in I_{1}},1_{v\in I_{2}},\ldots,1_{v\in I_{k}}\right)$.
Since every vertex belongs to at least one maximal independent set, no vertex
gets assigned the zero vector. Moreover, Lemma 6 shows that no two vertices
have the same associated vector, as $G$ is assumed to be twin-free. Since
there are only $2^{k}-1$ distinct non-zero vectors, we conclude that $n\leq
2^{k}-1$, i.e., $k>\log_{2}(n)$. ∎

This argument is further refined in the following subsection.

###  2.1 Proof of Theorem 2

Let us now prove Theorem 2, whose statement we first recall.

######  Theorem 2.

Let $k\geq 2$ be an integer. If $G$ is a connected twin-free graph with $n$
vertices and $i_{\text{max}}(G)=k$, then $n\leq 2^{k-1}+k-2$. Furthermore,
equality holds only if the graph $G$ is formed by taking a clique $K_{k-1}$
and adding, for every non-empty vertex subset $S$ of this clique, a vertex
whose neighbourhood is precisely $S$.

For $k=2$, the statement holds by Proposition 7 and the fact that
$i_{max}(K_{3})=3>2.$

Suppose for contradiction that Theorem 2 does not hold, and let $k\geq 3$ be
the minimum value for which this is the case. Let $G$ be a graph of maximum
order for which $i_{\text{max}}(G)=k$, and let $I_{1},\ldots,I_{k}$ be its
maximal independent sets. As in the proof of Proposition 7, we can conclude
that every vertex of $G$ belongs to at least one of these sets.

######  Lemma 8.

Every maximal independent set $I_{i}$ has a vertex $u_{i}$ that belongs to no
maximal independent set $I_{j}$ with $j\neq i$.

###### Proof.

If this is not the case, add a vertex $u_{i}$ to the graph that is adjacent to
all vertices except those in $I_{i}$. Then $I_{i}$ is extended by this new
vertex, but all other maximal independent sets remain the same. Note that the
new vertex does not belong to any maximal independent sets other than the
extension of $I_{i}$. By Lemma 6, the new graph $G^{\prime}$ is still twin-
free, and $i_{\text{max}}(G^{\prime})=i_{\text{max}}(G)$, contradicting the
choice of $G$. ∎

######  Lemma 9.

In every graph $H$, we have $i_{\text{max}}(H)\geq\chi(H)\geq\omega(H)$.

###### Proof.

It is sufficient to observe that every colour class of an optimal proper
colouring is an independent set, but the union of two colour classes is not.
Since every independent set can be (e.g. greedily) extended to at least one
maximal independent set, $i_{\text{max}}(H)\geq\chi(H)$ is immediate. The
inequality $\chi(H)\geq\omega(H)$ is well known. ∎

In the graph $G$ that we took as counterexample to Theorem 2, any two vertices
$u_{i}$ and $u_{j}$ as defined in Lemma 8 with $i\neq j$ have to be adjacent.
Otherwise, $\\{u_{i},u_{j}\\}$ could be extended to a maximal independent set,
contradicting the choice of $u_{i}$ and $u_{j}$. So
$U=\\{u_{1},\ldots,u_{k}\\}$ spans a complete graph, implying that
$\omega(G)\geq k=i_{\text{max}}(G)$, which means that we have equality in
Lemma 9 when applied to $G$.

######  Lemma 10.

A vertex $v\not\in U$ belongs to $I_{j}$ if and only if it is not adjacent to
$u_{j}$.

###### Proof.

If $v$ belongs to $I_{j}$, then it can clearly not be adjacent to $u_{j}$
(which also belongs to $I_{j}$). Conversely, if $v,u_{j}$ are not adjacent,
then $\\{v,u_{j}\\}$ can be extended to a maximal independent set, which must
necessarily be $I_{j}$ (by Lemma 8). ∎

Remembering that the vectors $\vec{v}$ as defined in the proof of Proposition
7 are all distinct and neither equal to the all-$0$ vector (as every vertex
belongs to a maximal independent set) nor the all-$1$ vector (the
corresponding vertex would be isolated), we know that every vertex has at
least one neighbour in the clique induced by $U$, and no two vertices
$v,v^{\prime}\notin U$ satisfy $N(v)\cap U=N(v^{\prime})\cap U$.

######  Lemma 11.

Two vertices $v,v^{\prime}\notin U$ are adjacent if and only if $U\subseteq
N(v)\cup N(v^{\prime})$.

###### Proof.

If $v,v^{\prime}$ are adjacent and $u\in U$ does not belong to $N(v)\cup
N(v^{\prime})$, then $\\{u,v\\}$ and $\\{u,v^{\prime}\\}$ can be extended to
distinct maximal independent sets containing $u$. This contradicts the
construction of $U$ (Lemma 8), so $U\subseteq N(v)\cup N(v^{\prime})$ in this
case.

Conversely, if $v,v^{\prime}$ are not adjacent, then the set
$\\{v,v^{\prime}\\}$ can be extended to a maximal independent set, which must
contain a vertex of $U$ by construction. As this vertex is not in $N(v)\cup
N(v^{\prime})$, $U$ is not fully contained in $N(v)\cup N(v^{\prime})$ in this
case. ∎

If the union of the neighbourhoods of the vertices in an independent set in
$V(G)\setminus U$ contains all of $U$, it can be extended to a maximal
independent set without any vertices in $U$, leading to a contradiction again.
Equivalently, if the union of the neighbourhoods of some vertices in
$V(G)\setminus U$ contains all of $U$, then it cannot be an independent set,
so it must contain two adjacent vertices whose neighbourhoods cover $U$ by
Lemma 11. This observation naturally leads us to the following concept.

######  Definition 12.

We call a family $\mathcal{F}\subseteq 2^{[n]}$ _union-efficient_ if for every
subfamily $\\{A_{1},\ldots,A_{m}\\}$ of $\mathcal{F}$ for which
$\cup_{i\in[m]}A_{i}=[n]$, there are two indices $i,j\in[m]$ for which
$A_{i}\cup A_{j}=[n].$

For every vertex $v_{i}\in V(G)\setminus U$, we consider the index set
$A_{i}=\\{j\mid u_{j}\in N(v_{i}),1\leq j\leq k\\}$. As explained before, the
family $\mathcal{F}\subseteq 2^{[k]}$ consisting of all these $A_{i}$ is
union-efficient.

Note that $\mathcal{F}$ does not include $\emptyset,[k]$ (as observed before),
nor $[k]\setminus j$ for any $j\in[k]$. The latter holds because
$A_{i}=[k]\setminus j$ would mean that $v_{i}$ is adjacent to (a) all vertices
in $U$ except $u_{j}$, and (b) precisely those vertices in $V(G)\setminus U$
that are adjacent to $u_{j}$ (by Lemma 11). But then $v_{i}$ and $u_{j}$ would
be twins, a contradiction. It is easy to see that $\mathcal{F}$ stays union-
efficient if we add these $k+2$ sets to $\mathcal{F}$.

Formulated in the terminology of union-efficient families (the equivalence is
explained in [2]), the following theorem is a result by Milner (see [5]), with
the uniqueness result proven by Bollobás and Duchet [1], and by Mulder [17].

######  Theorem 13.

Let $n\geq 3$, and let $\mathcal{F}\subseteq 2^{[n]}$ be a union-efficient
family. Then $\lvert\mathcal{F}\rvert\leq 2^{n-1}+n.$ Equality is attained if
and only if (up to isomorphism) $\mathcal{F}=2^{[n-1]}\cup\binom{[n]}{\geq
n-1}$ (i.e., $\mathcal{F}$ contains all subsets of $[n-1]$ and all subsets of
$[n]$ with at least $n-1$ elements).

Theorem 13 implies that $\lvert\mathcal{F}\rvert\leq 2^{k-1}-2$, thus

$|V(G)|=|U|+|V(G)\setminus U|\leq k+2^{k-1}-2,$

and equality holds if and only if (up to renaming)
$\mathcal{F}=2^{[k-1]}\setminus\\{[k-1],\emptyset\\}$. In this case, $G$
consists of the clique induced by $u_{1},\ldots,u_{k-1}$ and the $2^{k-1}-1$
vertices in $V(G)\setminus\\{u_{1},\ldots,u_{k-1}\\}$ whose neighbourhoods are
precisely all the different nonempty subsets of $\\{u_{1},\ldots,u_{k-1}\\}$
($u_{k}$ is the unique vertex adjacent to all of them). This is precisely the
characterization of the extremal graph described in Theorem 2, completing our
proof.

Note that connectedness was only used in one place in our entire proof: to
rule out isolated vertices. If we drop this condition, we obtain the following
version of Theorem 2.

######  Corollary 14.

Let $k\geq 2$ be an integer. If $G$ is a twin-free graph with $n$ vertices and
$i_{\text{max}}(G)=k$, then $n\leq 2^{k-1}+k-1$. Furthermore, equality holds
only if the graph $G$ is formed by taking a clique $K_{k-1}$ and adding, for
every vertex subset $S$ of this clique, a vertex whose neighbourhood is
precisely $S$.

##  3 Twin-free bipartite graphs

In this section, we show that the minimum value of $i_{\text{max}}(G)$ for
twin-free bipartite graphs is linear in its order. We start by proving Theorem
3, which we recall for convenience.

######  Theorem 3.

Let $G$ be a connected twin-free bipartite graph of order $n\geq 2$. Then
$i_{\text{max}}(G)\geq\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}+1$,
and this inequality is sharp.

###### Proof.

For the lower bound, we prove a stronger statement: if $G$ is a twin-free
bipartite graph without isolated vertices whose bipartition classes $A,B$ have
size $a\leq b$ ($b\leq 2^{a}-1$ is necessary for existence), then
$i_{\text{max}}(G)\geq b+1.$

For every vertex $v\in B$, consider the set $I_{v}=(A\setminus
N(v))\cup\\{u\in B\mid N(u)\subseteq N(v)\\}$. This is a maximal independent
set by construction. Since for every two vertices $u,v\in B$ their
neighbourhoods $N(u)$ and $N(v)$ are different, we have $I_{u}\neq I_{v}$ if
$u\neq v.$ Finally, $A$ is also a maximal independent set (since $G$ has no
isolated vertices) that does not coincide with any of the $I_{v}$. Thus $G$
has at least $b+1$ maximal independent sets. Since
$b\geq\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{},$ the lower
bound is clear.

Equality is attained for example by taking a balanced complete bipartite graph
$K_{\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{},\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}}$
and removing a matching $M$ of size
$\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}-1$. The graph
$K_{\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{},\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}}\setminus
M$ is clearly bipartite, connected and twin-free (note that a bipartite graph
is twin-free if and only if its bipartite complement is). It has two types of
maximal independent sets: each of the bipartition classes is a maximal
independent set, and for each of the
$\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}-1$ edges in $M$,
the ends form a maximal independent set of cardinality $2$. There are no
others: once two vertices from the same bipartition class are contained in an
independent set $I$, no vertices from the other class can be included. By
maximality, $I$ must be one of the bipartition classes in this case. If an
independent set $I$ contains vertices from both classes, then they have to be
the ends of an edge in $M$, as they would otherwise be adjacent. Hence
$i_{\text{max}}\left(K_{\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{},\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}}\setminus
M\right)=\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}+1$. ∎

The same bound seems to hold more generally for triangle-free graphs, but we
do not have a proof at this point.

######  Conjecture 15.

Let $G$ be a connected, twin-free and triangle-free graph of order $n$. Then
$i_{\text{max}}(G)\geq\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}+1.$
Furthermore, if $n$ is even, graphs that attain equality are bipartite.

If we drop the condition of connectedness, it only changes the minimum by at
most $1$ (the same is true for triangle-free graphs under Conjecture 15),
since we only needed to consider graphs without isolated vertices in our
proof. A twin-free graph can clearly only contain at most one isolated vertex,
so the following corollary is immediate.

######  Corollary 16.

For every twin-free bipartite graph $G$ of order $n$, we have
$i_{\text{max}}(G)\geq\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{}+1$,
and this inequality is sharp.

The graphs in the proof that were constructed to show that the inequality is
sharp are not unique—there are many more extremal graphs, see Table 1.

$n$ | $\min i_{\text{max}}(G)$ | # extremal bip. graphs | # extremal $K_{3}$-free graphs
---|---|---|---
4 | 3 | 1 | 1
5 | 4 | 1 | 1
6 | 4 | $2$ | 2
7 | 5 | $4$ | 5
8 | 5 | 4 | 4
9 | 6 | 16 | 18
10 | 6 | 11 | 11
11 | 7 | 73 | 79
12 | 7 | 33 | 33
Table 1: The number of connected twin-free bipartite/triangle-free graphs for
which the minimum in Theorem 3 is attained.

Let us also present a bijection with certain binary matrices.

######  Proposition 17.

The connected twin-free bipartite graphs of order $2k$ for which
$i_{\text{max}}(G)=k+1$ are in one-to-one correspondence with $k\times
k$-binary matrices satisfying the following conditions:

  * •

there is an all-$1$ row and an all-$1$ column,

  * •

all columns are distinct, and all rows are distinct,

  * •

the union (bitwise maximum) of any two rows is a row of the matrix itself.

###### Proof.

By the proof of Theorem 3, the equality $i_{\text{max}}(G)=k+1$ can only occur
among balanced bipartite graphs. The bipartite graph can now be presented by
its reduced adjacency matrix $\mathcal{M}$, which is a $k\times k$-matrix.
From the proof, we also conclude that there is a vertex $v\in B$ for which
$I_{v}=B$ and thus $N(v)=A.$ Similarly, there is a vertex $w\in A$ with
$N(w)=B$. Thus $\mathcal{M}$ has a row and a column containing only $1$s. The
graph $G$ being twin-free is equivalent to $\mathcal{M}$ having distinct rows
and distinct columns.

If there is a bipartition class, say $B$, of $G$ for which the union of the
neighbourhoods of some of its vertices, $B_{1}\subseteq B$
($B_{1}\not=\emptyset$), is not equal to the neighbourhood of a vertex in $B$,
then $A\setminus N(B_{1})\cup\\{u\in B\mid N(u)\subseteq N(B_{1})\\}$ would be
another maximal independent set not counted in the proof of Theorem 3. So for
every $B_{1}\subseteq B$, there is a $b\in B$ with $N(B_{1})=N(b).$ The latter
is the case if and only if this is true for every subset $B_{1}$ of size $2,$
which is equivalent with the union of any $2$ rows being a row itself.

In the reverse direction, assuming $\mathcal{M}$ does satisfy the conditions,
we know that it is the adjacency matrix of a connected twin-free bipartite
graph $G$. Assume a maximal independent set of $G$ different from $A$ consists
of precisely the vertices in $A_{1}\subseteq A$ and $B_{1}\subseteq B$. Due to
the third condition, there is a vertex $b$ for which $N(B_{1})=N(b).$ Then
$B_{1}$ has to be precisely equal to $\\{u\in B\mid N(u)\subseteq N(b)\\}$,
and $A_{1}=A\backslash N(b)$ since $A_{1}\cup B_{1}$ is a maximal independent
set. Therefore the maximal independent sets are exactly those of the form
$\\{I_{b}\mid b\in B\\}\cup\\{A\\}$, and we have $i_{\text{max}}(G)=k+1$. We
conclude that we really have a bijection. ∎

######  Remark 18.

This also gives a combinatorial proof that among square binary matrices
$\mathcal{M}$ with all columns resp. rows distinct and containing an all-$1$
row and an all-$1$ column, the condition that the union of columns of
$\mathcal{M}$ is a column of $\mathcal{M}$ is equivalent with the condition
that the union of any choice of rows of $\mathcal{M}$ is a row of
$\mathcal{M}$.

From this characterization, it can be derived that there are at least
exponentially many bipartite graphs $G$ of order $2k$ for which
$i_{\text{max}}(G)=k+1$. For example,
$2^{\mathopen{}\left\lfloor\frac{k}{3}\right\rfloor\mathclose{}}$ different
matrices satisfying the constraints in Proposition 17 can be obtained by
taking a $k\times k$ binary lower-triangular matrix $\mathcal{M}$ all of whose
lower-triangular elements are $1$ and then additionally setting some entries
$\mathcal{M}_{3i+1,3i+3}$ equal to $1$ for some $1\leq
i\leq\mathopen{}\left\lfloor\frac{k}{3}\right\rfloor\mathclose{}.$ For $k=6$,
this gives four possibile matrices of this form (a red entry can be either $0$
or $1$)

$\mathcal{M}=\begin{pmatrix}1&0&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0/1}&0&0&0\\\
1&1&0&0&0&0\\\ 1&1&1&0&0&0\\\
1&1&1&1&0&{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0/1}\\\
1&1&1&1&1&0\\\ 1&1&1&1&1&1\\\ \end{pmatrix}.$

##  4 Twin-free trees

In this section, we will consider the problem for trees. Let us start again by
recalling the theorem we want to prove. We first define a function $f$ by
$f(1)=1,f(2)=f(3)=2$, and for $n\geq 4$

$f(n)=\begin{cases}4\cdot 3^{\frac{n}{5}-1}&\text{ if }n\equiv 0\pmod{5},\\\
5\cdot 3^{\frac{n-6}{5}}&\text{ if }n\equiv 1\pmod{5},\\\ 2\cdot
3^{\frac{n-2}{5}}&\text{ if }n\equiv 2\pmod{5},\\\ 8\cdot
3^{\frac{n-8}{5}}&\text{ if }n\equiv 3\pmod{5},\\\ 3^{\frac{n+1}{5}}&\text{ if
}n\equiv 4\pmod{5}.\end{cases}$

The main theorem of this section can thus be stated as follows.

######  Theorem 4.

Let $n\geq 4$ be an integer. Then for every twin-free tree $T$ with $n$
vertices, we have $i_{\text{max}}(T)\geq f(n)$, and this inequality is sharp.

Note that the inequality $i_{\text{max}}(T)\geq f(n)$ is also true for
$n\in\\{1,2,3\\}$, although the statement is void for $n=3$ as there are no
twin-free trees with $3$ vertices (however, $i_{\text{max}}(P_{3})=2$).

For $n\leq 10$, the values can be verified by determining $i_{\text{max}}(T)$
for all trees of order $n$ (these are the base cases of our induction proof).
So from now on, we consider $n\geq 11$ and assume that the statement has been
proven for every smaller order.

In the proof of Theorem 4, we will frequently use the following estimates.

######  Lemma 19.

The following statements hold:

  1. (a)

except for the pair $(n,m)=(3,3)$, we have $f(n)\cdot f(m)\geq f(n+m)$ for all
$n,m\geq 2$, and

  2. (b)

$f(n-1)\cdot f(m-1)\geq f(n+m-1)$ for all $n,m\geq 5.$

###### Proof.

Note that for $n\geq 5$, the function $g(n)=f(n-1)3^{-\frac{n}{5}}\geq 1$ only
depends on the residue class modulo $5$, namely

$g(n)=\begin{cases}1&\text{ if }n\equiv 0\pmod{5},\\\ 4\cdot
3^{-\frac{6}{5}}&\text{ if }n\equiv 1\pmod{5},\\\ 5\cdot
3^{-\frac{7}{5}}&\text{ if }n\equiv 2\pmod{5},\\\ 2\cdot
3^{-\frac{3}{5}}&\text{ if }n\equiv 3\pmod{5},\\\ 8\cdot
3^{-\frac{9}{5}}&\text{ if }n\equiv 4\pmod{5}.\\\ \end{cases}$

A direct verification shows that

$\frac{g(i)g(j)}{g(i+j)}\in\Big{\\{}1,\frac{25}{24},\frac{16}{15},\frac{10}{9},\frac{32}{27}\Big{\\}},$

thus in particular $g(i)g(j)\geq g(i+j)$ in all cases. So it follows that

$f(n-1)f(m-1)=3^{(n+m)/5}g(n)g(m)\geq 3^{(n+m)/5}g(n+m)=f(n+m-1)$

for all $n,m\geq 5$. Thus statement (b) holds. Since $f(n)$ is increasing for
$n\geq 4$, we have

$f(n)f(m)\geq f(n+m+1)>f(n+m)$

for all $n,m\geq 4$. Thus we only need to verify (a) in those cases where
either $n$ or $m$ (without loss of generality $n$) is equal to $2$ or $3$. If
both $n$ and $m$ are equal to $2$ or $3$, then the inequality holds unless
$n=m=3$, as $f(6)=5>f(2)^{2}=f(2)f(3)=f(3)^{2}=4=f(5)>f(4)=3$.

Moreover, since $f(2)=f(3)=2$, it actually suffices to consider $n=3$ (again
because $f$ is an increasing function: $f(3)f(m)\geq f(m+3)$ implies
$f(2)f(m)=f(3)f(m)\geq f(m+2)$). The inequality $f(3)f(m)=2f(m)\geq f(m+3)$ is
easily verified for $m\geq 4$ by checking all five possible cases modulo $5$
and finding that

$\frac{f(3)f(m)}{f(3+m)}\in\Big{\\{}1,\frac{16}{15},\frac{10}{9}\Big{\\}}.$

∎

Next, we explain the inductive idea used by Wilf [20]. Let $x$ be a leaf of
$T$ and $y$ its neighbour. Let $u_{1},u_{2},\ldots,u_{r}$ be the neighbours of
$y$ different from $x$. Let $U_{i}$ be the component (subtree) of
$T\setminus\\{x,y\\}$ that contains $u_{i}$, and let $W_{i,j}$, $1\leq j\leq
s_{i}$, be the components of $U_{i}\setminus u_{i}$. Finally, let $w_{i,j}$ be
the neighbour of $u_{i}$ belonging to $W_{i,j}.$ This is illustrated in Figure
6.

$\ldots$$\ldots$$\ldots$$\cdots$$x$$y$$u_{1}$$u_{2}$$u_{r}$$w_{1,1}$$w_{1,s_{1}}$$w_{2,1}$$w_{2,s_{2}}$$w_{r,s_{r}}$$w_{r,1}$$W_{1,1}$$W_{1,s_{1}}$$W_{2,1}$$W_{2,s_{2}}$$W_{r,s_{r}}$$W_{r,1}$$U_{1}$$U_{2}$$U_{r}$
Figure 6: Tree with subtrees.

Then the following result holds, see [20, Lemma 1].

######  Lemma 20 ([20]).

If $T$ is a tree decomposed as in Figure 6, then

$i_{\text{max}}(T)=\prod_{i=1}^{r}i_{\text{max}}(U_{i})+\prod_{i=1}^{r}\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j}).$

With this formula, it is immediate to prove that the five constructions in
Figure 4 give equality in Theorem 4.

Let us now continue with our induction proof. Assume that $T$ is a twin-free
tree of order $n\geq 11$. Choose a leaf $x$, and decompose $T$ according to
Figure 6. Since $T$ cannot have two leaves with the same neighbour due to the
condition of being twin-free, we know that every component $U_{i}$ satisfies
$\lvert U_{i}\rvert\geq 2$.

The core of our induction is included in the following lemma.

######  Lemma 21.

Let $\lvert U_{i}\rvert=m$, where $m\geq 7$. Then at least one of the
following holds:

  1. 1.

$i_{\text{max}}(U_{i})\geq f(m-1)$ and
$\displaystyle\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})\geq f(m-1)$, or

  2. 2.

$i_{\text{max}}(U_{i})\geq f(m)$ and
$\displaystyle\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})\geq f(m-2)$, or

  3. 3.

$i_{\text{max}}(U_{i})\geq 2f(m-3)$ and
$\displaystyle\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})\geq f(m-3)$.

###### Proof.

We divide the proof into two cases, depending on the root degree of $U_{i}$.

Case 1: $s_{i}=1$.
Observe that if $U_{i}$ is not twin-free (in which case $u_{i}$ and a leaf of
$U_{i}$ are at distance $2$ from each other), then $W_{i,1}$ is twin-free and
by the induction hypothesis $i_{\text{max}}(U_{i})=i_{\text{max}}(W_{i,1})\geq
f(m-1)$, so the first of the three statements holds. If $U_{i}$ is twin-free,
$W_{i,1}$ might not be, but can in this case be made twin-free by removing a
vertex without affecting $i_{\text{max}}$. Hence we have
$i_{\text{max}}(U_{i})\geq f(m)$ and $i_{\text{max}}(W_{i,1})\geq f(m-2)$, so
the second statement holds.

Case 2: $s_{i}\geq 2$.
First we observe that $U_{i}$ is now always a twin-free tree and thus
$i_{\text{max}}(U_{i})\geq f(m)$ by the induction hypothesis. We also observe
that $i_{\text{max}}(W_{i,j})\geq f(\lvert W_{i,j}\rvert)$ if $W_{i,j}$ is
twin-free and otherwise $i_{\text{max}}(W_{i,j})\geq f(\lvert
W_{i,j}\rvert-1)$ by the same argument as in Case 1.

If $\lvert W_{i,j}\rvert\leq 4$, then we have
$i_{\text{max}}(W_{i,j})=f(\lvert W_{i,j}\rvert)$: in each case, there is only
one possible tree up to isomorphism ($W_{i,j}$ cannot be a star of order $4$,
since $T$ would then not be twin-free). Hence
$i_{\text{max}}(W_{i,j})<f(\lvert W_{i,j}\rvert)$ can only happen if $\lvert
W_{i,j}\rvert\geq 5$.

We consider two subcases now: assume first that $\lvert W_{i,j}\rvert>1$ for
all $j$. We have $i_{\text{max}}(W_{i,j})\geq f(\lvert W_{i,j}\rvert-1)$
whenever $\lvert W_{i,j}\rvert\geq 5$, and iterating part (b) of Lemma 19
gives us

$\prod_{j:\lvert W_{i,j}\rvert\geq 5}i_{\text{max}}(W_{i,j})\geq
f\left(\left(\sum_{j:\lvert W_{i,j}\rvert\geq 5}W_{i,j}\right)-1\right),$

provided there are $W_{i,j}$ of order $5$ or greater. For all $j$ with
$W_{i,j}<5$, we can use the fact that $i_{\text{max}}(W_{i,j})=f(\lvert
W_{i,j}\rvert)$. Applying part (a) of the same lemma repeatedly now, we end up
with

$\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})\geq
f\left(\left(\sum_{j=1}^{s_{i}}W_{i,j}\right)-1\right)=f(m-2),$ (1)

so statement 2 holds in this case. If there are no $W_{i,j}$ of order $5$ or
greater, we can skip the first step and only apply part (a) of Lemma 19. The
exceptional case $(3,3)$ only occurs at most once in the process, and we have
$f(3)^{2}=4=f(5)$, thus (1) still applies. In either case, we are done.

Let us finally consider the case that there is a $j$ (without loss of
generality $j=1$) such that $\lvert W_{i,j}\rvert=1$. There can only be one,
as $T$ is assumed to be twin-free. The same argument as in the other subcase
now yields

$\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})=\prod_{j=2}^{s_{i}}i_{\text{max}}(W_{i,j})\geq
f\left(\sum_{j=2}^{s_{i}}W_{i,j}-1\right)=f(m-3).$

Moreover, this bound can be improved if there is a twin-free $W_{i,j}$ of
order at least 4: in this case, we have $i_{\text{max}}(W_{i,j})\geq f(\lvert
W_{i,j}\rvert)$. Iterating part (b) of Lemma 19 then yields

$\prod_{j:\lvert W_{i,j}\rvert\geq 4}i_{\text{max}}(W_{i,j})\geq
f\left(\sum_{j:\lvert W_{i,j}\rvert\geq 4}W_{i,j}\right)$

and thus (1) again, in which case we are done. Likewise, since $f(2)=f(3)=2$,
we can improve the bound to $f(m-2)$ if there is a $W_{i,j}$ of order $2$.

So if (1) does not hold, then $W_{i,j}$ cannot be twin-free for any $j\geq 2$
(there are no twin-free trees of order $3$, and all other orders have been
ruled out). This is only possible if the degree of $w_{i,j}$ is $2$. Moreover,
$i_{\text{max}}(W_{i,j}\setminus w_{i,j})=i_{\text{max}}(W_{i,j})$ in this
case. Taking $w_{i,1}$ (which by our assumption is a leaf) as the new root, we
can apply Lemma 21 to $U_{i}$ and deduce that

$i_{\text{max}}(U_{i})=\prod_{j=2}^{s_{i}}i_{\text{max}}(W_{i,j})+\prod_{j=2}^{s_{i}}i_{\text{max}}(W_{i,j}\setminus
w_{i,j})=2\prod_{j=2}^{s_{i}}i_{\text{max}}(W_{i,j})\geq 2f(m-3).$

Thus statement 3 applies in this case, which completes the proof. ∎

Lemma 21 can be rephrased as follows: if $\lvert U_{i}\rvert=m\geq 7$, then
the pair $(i_{\text{max}}(U_{i}),\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j}))$
is componentwise greater than or equal to one of $(f(m-1),f(m-1))$,
$(f(m),f(m-2))$ or $(2f(m-3),2f(m-3))$. These three possibilities are shown in
Table 2.

$m\pmod{5}$ | $(f(m-1),f(m-1))$ | $(f(m),f(m-2))$ | $(2f(m-3),f(m-3))$
---|---|---|---
0 | $(9,9)\cdot 3^{(m-10)/5}$ | $(12,8)\cdot 3^{(m-10)/5}$ | $(12,6)\cdot 3^{(m-10)/5}$
1 | $(12,12)\cdot 3^{(m-11)/5}$ | $(15,9)\cdot 3^{(m-11)/5}$ | $(16,8)\cdot 3^{(m-11)/5}$
2 | $(5,5)\cdot 3^{(m-7)/5}$ | $(6,4)\cdot 3^{(m-7)/5}$ | $(6,3)\cdot 3^{(m-7)/5}$
3 | $(6,6)\cdot 3^{(m-8)/5}$ | $(8,5)\cdot 3^{(m-8)/5}$ | $(8,4)\cdot 3^{(m-8)/5}$
4 | $(8,8)\cdot 3^{(m-9)/5}$ | $(9,6)\cdot 3^{(m-9)/5}$ | $(10,5)\cdot 3^{(m-9)/5}$
Table 2: The three possibilities in Lemma 21.

Now consider the case that $\lvert U_{i}\rvert=m$ with $2\leq m\leq 6$. All
resulting possibilities for the pair
$(i_{\text{max}}(U_{i}),\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j}))$ are
listed in Table 3.

$m$ | $\left(i_{\text{max}}(U_{i}),\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})\right)$
---|---
2 | $(2,1)$
3 | $(2,2)$
4 | $(3,2)$
5 |  $(4,4)$ or $(4,3)$ or $(4,2)$ or $(3,3)$
6 |  $(5,4)$, $(5,3)$ or $(4,4)$
Table 3: The possibilities for the two $i_{\text{max}}$ values for $2\leq
m\leq 6$.

Next we define some notation: we say that $(a,b)$ _majorizes_
$(a^{\prime},b^{\prime})$ if $a\geq a^{\prime}$ and $a+b\geq
a^{\prime}+b^{\prime}$. This is denoted by
$(a,b)\succeq(a^{\prime},b^{\prime})$. Note that this is a transitive
relation, and that $(a,b)\geq(a^{\prime},b^{\prime})$ (componentwise) implies
$(a,b)\succeq(a^{\prime},b^{\prime})$. We can combine Lemma 21 and the small
cases in Table 3 to the following lemma (for its proof, simply notice that the
other entries in Table 2 and Table 3 themselves majorize one of the given
pairs).

######  Lemma 22.

If $\lvert U_{i}\rvert=m\geq 2$, then the pair
$(i_{\text{max}}(U_{i}),\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j}))$ majorizes
one of the pairs given in Table 4.

$m\pmod{5}$ | majorized pairs
---|---
0 | $(9,9)\cdot 3^{(m-10)/5}$
1 | $(12,12)\cdot 3^{(m-11)/5}$
2 |  $(5,5)\cdot 3^{(m-7)/5}$ or $(6,3)\cdot 3^{(m-7)/5}$
3 | $(6,6)\cdot 3^{(m-8)/5}$
4 |  $(8,8)\cdot 3^{(m-9)/5}$ or $(9,6)\cdot 3^{(m-9)/5}$
Table 4: The possibilities in Lemma 22.

The following property of majorization is straightforward; we provide its
proof for completeness.

######  Lemma 23.

If $(a,b)\succeq(a^{\prime},b^{\prime})$ and
$(c,d)\succeq(c^{\prime},d^{\prime})$ for nonnegative
$a,b,c,d,a^{\prime},b^{\prime},c^{\prime},d^{\prime}$, where $a^{\prime}\geq
b^{\prime}$ and $c^{\prime}\geq d^{\prime}$, then
$(ac,bd)\succeq(a^{\prime}c^{\prime},b^{\prime}d^{\prime})$.

###### Proof.

The inequality $ac\geq bd$ is trivial. For the second inequality, consider
first the case that $d\geq c$. Then we have

$ac+bd\geq(a+b)c\geq(a^{\prime}+b^{\prime})c\geq
a^{\prime}c^{\prime}+b^{\prime}d^{\prime},$

since $a+b\geq a^{\prime}+b^{\prime}$ and $c\geq c^{\prime}\geq d^{\prime}$ by
assumption. Otherwise, we have $c\geq d$ and find

$ac-a^{\prime}c^{\prime}=(a-a^{\prime})c+a^{\prime}(c-c^{\prime})\geq(b^{\prime}-b)d+b^{\prime}(d^{\prime}-d)=b^{\prime}d^{\prime}-bd,$

since $a-a^{\prime}\geq b^{\prime}-b$, $c\geq d$, $a^{\prime}\geq b^{\prime}$
and $c-c^{\prime}\geq d^{\prime}-d$ as well as $a-a^{\prime}\geq 0$ and
$c-c^{\prime}\geq 0$. Again, the inequality $ac+bd\geq
a^{\prime}c^{\prime}+b^{\prime}d^{\prime}$ follows. ∎

Set $A_{0}=\\{(1,1)\\}$, $A_{1}=\\{(4\cdot 3^{-6/5},4\cdot 3^{-6/5})\\}$,
$A_{2}=\\{(5\cdot 3^{-7/5},5\cdot 3^{-7/5}),(2\cdot 3^{-2/5},3^{-2/5})\\}$,
$A_{3}=\\{(2\cdot 3^{-3/5},2\cdot 3^{-3/5})\\}$ and $A_{4}=\\{(8\cdot
3^{-9/5},8\cdot 3^{-9/5}),(3^{1/5},2\cdot 3^{-4/5})\\}$. For $m>4$, continue
the definition of $A_{m}$ by taking indices modulo $5$. Lemma 22 can be
restated as follows: if $|U_{i}|=m\geq 2$, then
$3^{-m/5}(i_{\text{max}}(U_{i}),\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j}))$
majorizes one of the pairs in $A_{m}$. The following can be verified directly
by checking all possible combinations.

######  Lemma 24.

Let $i,j$ be nonnegative integers, and suppose that $(a,b)\in A_{i}$ and
$(c,d)\in A_{j}$. Then $(ac,bd)\succeq(x,y)$ for some $(x,y)\in A_{i+j}$.

The next lemma is now obtained by a straightforward induction on $k$.

######  Lemma 25.

Let $k$ be a positive integer, and $m=\sum_{i=1}^{k}|U_{i}|$. Then the pair

$3^{-m/5}\left(\prod_{i=1}^{k}i_{\text{max}}(U_{i}),\prod_{i=1}^{k}\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})\right)$

majorizes some $(x,y)\in A_{m}$.

In particular, taking $k=r$ (with $r$ as in Lemma 20), we have
$m=\sum_{i=1}^{r}|U_{i}|=|T|-2=n-2$ and finally obtain from the formula in
Lemma 20 that

$i_{\text{max}}(T)=\prod_{i=1}^{r}i_{\text{max}}(U_{i})+\prod_{i=1}^{r}\prod_{j=1}^{s_{i}}i_{\text{max}}(W_{i,j})\geq
3^{(n-2)/5}(x+y)$

for some $(x,y)\in A_{n-2}$. In all five cases modulo $5$, the inequality
$i_{\text{max}}(T)\geq f(n)$ follows immediately as a consequence, which
finally completes the proof of Theorem 4.

Theorem 4 also easily extends to forests, as the following corollary shows.

######  Corollary 26.

For every twin-free forest $F$ of order $n\geq 2$, we have
$i_{\text{max}}(F)\geq f(n-1)$.

###### Proof.

We use induction on $n$. For $n\leq 4$, the inequality is easy to check, so
let us consider $n\geq 5$. Suppose that $F$ is disconnected and has a
connected component $T$ of order $m$ with $n-1>m\geq 2$. Taking the smallest
such component, we can assume that $m\leq\frac{n}{2}$ and thus
$n-m\geq\mathopen{}\left\lceil\frac{n}{2}\right\rceil\mathclose{}\geq 3$. By
Theorem 4 and the induction hypothesis, we have

$i_{\text{max}}(F)=i_{\text{max}}(T)\cdot i_{\text{max}}(F-T)\geq f(m)\cdot
f(n-m-1)\geq f(n-1),$

where the final inequality follows from part (a) of Lemma 19. Note here that
$m\neq 3$, since there are no twin-free trees of order $3$. The only remaining
possibilities are that $F$ is connected (i.e., a tree), or that $F$ consists
of a tree and one isolated vertex. In either case, the conclusion follows from
Theorem 4. ∎

###  4.1 The extremal trees

The extremal trees can be constructed iteratively by tracking the cases of
equality in the proof. A complete characterization is provided in [19]. Here
we add a small correction for $n=8$: there are three extremal trees (rather
than two as claimed in [19]), see Figure 7.

Due to the different constructions, it is not too surprising that the number
of extremal trees is not monotone as a function of $n$. The number of extremal
trees for $4\leq n\leq 19$ is summarized in Table 5.

$n$ | # Extremal trees
---|---
$\\{4,5,7,9\\}$ | $1$
$\\{6,14\\}$ | $2$
$\\{8,10,11,12\\}$ | $3$
13 | $11$
$\\{15,16\\}$ | $12$
17 | $10$
18 | $60$
19 | $5$
Table 5: Number of extremal trees (i.e., trees satisfying
$i_{\text{max}}(T)=f(n)$) of order $n$. Figure 7: The three twin-free trees
for $n=8$ satisfying $i_{\text{max}}(T)=8$.

##  5 Further thoughts

Füredi [6, Conjecture 4.3] asked about the maximum of $i_{\text{max}}$ for
other graph classes. This was done e.g. for triangle-free graphs in [9, 3],
connected unicyclic graphs [13] and graphs with bounded degrees [14]. Let
$\max i_{\text{max}}(\mathcal{G})$ denote the maximum number of maximal
independent sets in a graph class $\mathcal{G}.$ This maximum grows
exponentially in all cases mentioned, and $\lim_{n\to\infty}(\max
i_{\text{max}}(\mathcal{G}))^{1/n}$ equals $\sqrt{2}$ and $\sqrt[3]{3}$ for
trees and graphs respectively.

In this paper, we proved that the minimum number of $i_{max}$ for twin-free
graphs, bipartite graphs and trees is logarithmic, linear and exponential,
respectively. Due to this big difference in behaviour of the minimum of
$i_{\text{max}}$, it may even be considered more interesting to study $\min
i_{\text{max}}(\mathcal{G})$ for some other graph classes $\mathcal{G}$
(restricted to twin-free graphs), since even the behaviour in terms of the
order may be unclear.

######  Question 27.

What is the behaviour of $\min i_{\text{max}}(\mathcal{G})$ for twin-free
graphs in a graph class $\mathcal{G}$?

One plausible interesting direction can be to wonder what happens for
$k$-partite graphs as $n\to\infty.$ For bipartite graphs, the bound was
linear, while the extremal construction in Theorem 4 satisfies
$\chi(G)\sim\log_{2}(n).$ Similarly, one can wonder about graphs with bounded
clique number, with Conjecture 15 as a particular case.

Let $\nu(G)$ be the size of a maximum induced matching in $G$. Since every
independent set can be extended to a maximal independent set and a set
containing one end of each edge in an induced matching is an independent set,
we conclude that $i_{\text{max}}(G)\geq 2^{\nu(G)}.$ Note that
$\nu(G)\geq\frac{Cn}{\Delta^{2}}$ (see [10]) grows linearly in $n$ for graphs
with fixed maximum degree independent of $n$. For such sparse graph classes
(bounded maximum degree independent of $n$), $\min i_{\text{max}}(G)$ is
exponential in terms of $n.$ Kahn and Park [11] proved that for hypercubes
$Q_{n}$ of order $N=2^{n}$, we have
$\lim_{n\to\infty}i_{\text{max}}(Q_{n})^{1/N}=2^{1/4}$, while also
$\nu(Q_{n})=\frac{N}{4}$ for every $n\geq 2$: in other words,
$i_{\text{max}}(Q_{n})$ is of the form $2^{(1+o(1))\nu(G)}$. Note here that
the hypercube $Q_{n}$ is a twin-free graph if $n\geq 3$. For the twin-free
trees in Figure 4, we note that
$\lim_{n\to\infty}i_{\text{max}}(T)^{1/n}=3^{1/5}$ while
$\nu(G)=\frac{n}{5}+1$ (when $5\mid n$), so here $2^{\nu(G)/n}$ is a lower
bound for the limit that is not sharp. Studying $\lim_{n\to\infty}(\min
i_{\text{max}}(\mathcal{G}))^{1/n}$ for twin-free graphs in a graph class
$\mathcal{G}$ might be interesting, especially if there was a natural graph
class for which the constant is larger than $3^{1/5}$. One natural graph class
to consider are $r$-regular graphs for fixed $r$. It is known that
$i_{\text{max}}(C_{n})=P(n),$ where $P(n)$ denotes the $n^{th}$ Perrin number,
which is defined by $P(0)=3,P(1)=0,P(2)=2$ and the relation
$P(n)=P(n-2)+P(n-3)$ for $n\geq 3.$ For $n\geq 3$, the quantity $P(n)^{1/n}$
is minimized by $n=4$, and the second smallest value is attained for $n=6$.
Since $C_{4}$ is not twin-free, for the class $\mathcal{G}$ of twin-free
$2$-regular graphs, $\lim_{n\to\infty}(\min
i_{\text{max}}(\mathcal{G}))^{1/n}=i_{\text{max}}(C_{6})^{1/6}=5^{1/6}$.

On the other side of the spectrum, when $G$ is $r$-regular with $r=n-1-t$,
i.e. $\overline{G}$ has small degree, the question may be interesting as well.
Such graphs satisfy $\frac{n}{t+1}\leq i_{\text{max}}\leq 2^{t}n.$ For
$t=n^{1/s}$ and $\overline{G}$ being the Cartesian product of $s$ $K_{t}$s, we
have for example that $i_{\text{max}}(G)\sim sn^{1-1/s}.$

There may well be quite a number of other problems where a parameter $A$ can
be unbounded in terms of another parameter $B$ if $A$ can increase when adding
twins while $B$ does not. This was for example also the obstruction in the
related problem for $\nu(G)$, see [12].

One further direction is the relation between the vertex covering number
$\tau(G)$ and $i_{\text{max}}(G).$ Hoang and Trung [8] proved that
$i_{\text{max}}(G)\leq 2^{\tau(G)}$ for every graph $G$. In the other
direction there is no such bound, since the complete bipartite graph $K_{n,n}$
satisfies $i_{\text{max}}(G)=2$ and $\tau(G)=n.$ When restricting to twin-free
graphs, we know that $\tau(G)\leq n-1<2^{i_{\text{max}}(G)}$ by Proposition 7
and thus $\tau(G)$ is bounded by a function of $i_{\text{max}}(G)$. So the
following question would tell us about the essential relationship between the
two parameters.

######  Question 28.

What is the maximum possible vertex covering number $\tau$ of a twin-free
graph with $i_{\text{max}}(G)=k$?

Plausible candidates are $\tau(G)=O(i_{\text{max}}(G)^{2})$, and for given
order $n$,
$\tau(G)-i_{\text{max}}(G)\leq\mathopen{}\left\lfloor\frac{n}{2}\right\rfloor\mathclose{}-3.$
The first bound is attained by the complement of the Cartesian product
$K_{r}\square K_{r}$ (one can connect every $K_{r}$ with an additional
vertex), and the second one by the complement of a cycle of $K_{3}$s (i.e., a
cycle $C_{r}$ for which every edge is connected to a new vertex).

## Acknowledgement

This project originated from the Mathematics Research Community workshop
“Trees in Many Contexts”, which was supported by the National Science
Foundation under Grant Number DMS $1916439$.

#### Open access statement.

For the purpose of open access, a CC BY public copyright license is applied to
any Author Accepted Manuscript (AAM) arising from this submission.

## References

  * [1] B. Bollobás and P. Duchet.  On Helly families of maximal size.  J. Combin. Theory Ser. B, 35(3):290–296, 1983.
  * [2] S. Cambie and N. Salia.  Set systems without a simplex, Helly hypergraphs and union-efficient families.  arXiv e-prints, page arXiv:2210.16211, Oct. 2022.
  * [3] G. J. Chang and M.-J. Jou.  The number of maximal independent sets in connected triangle-free graphs.  volume 197/198, pages 169–178. 1999.  16th British Combinatorial Conference (London, 1997).
  * [4] I. Charon, I. Honkala, O. Hudry, and A. Lobstein.  Structural properties of twin-free graphs.  Electron. J. Combin., 14(1):Research Paper 16, 15 pages, 2007.
  * [5] P. Erdős.  Topics in combinatorial analysis.  In Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing, pages 2–20, 1971.
  * [6] Z. Füredi.  The number of maximal independent sets in connected graphs.  J. Graph Theory, 11(4):463–470, 1987.
  * [7] J. R. Griggs, C. M. Grinstead, and D. R. Guichard.  The number of maximal independent sets in a connected graph.  Discrete Math., 68(2-3):211–220, 1988.
  * [8] D. T. Hoang and T. N. Trung.  Coverings, matchings and the number of maximal independent sets of graphs.  Australas. J. Combin., 73:424–431, 2019.
  * [9] M. Hujter and Z. Tuza.  The number of maximal independent sets in triangle-free graphs.  SIAM J. Discrete Math., 6(2):284–288, 1993.
  * [10] F. Joos.  Induced matchings in graphs of bounded maximum degree.  SIAM J. Discrete Math., 30(3):1876–1882, 2016.
  * [11] J. Kahn and J. Park.  The number of maximal independent sets in the Hamming cube.  Combinatorica, 2022.
  * [12] I. Kanj, M. J. Pelsmajer, M. Schaefer, and G. Xia.  On the induced matching problem.  J. Comput. System Sci., 77(6):1058–1070, 2011.
  * [13] K. M. Koh, C. Y. Goh, and F. M. Dong.  The maximum number of maximal independent sets in unicyclic connected graphs.  Discrete Math., 308(17):3761–3769, 2008.
  * [14] J. Liu.  Constraints on the number of maximal independent sets in graphs.  J. Graph Theory, 18(2):195–204, 1994.
  * [15] R. E. Miller and D. E. Muller.  A problem of maximum consistent subsets.  Technical report, IBM Research Report RC-240, JT Watson Research Center, Yorktown Heights, NY, 1960.
  * [16] J. W. Moon and L. Moser.  On cliques in graphs.  Israel J. Math., 3:23–28, 1965.
  * [17] H. M. Mulder.  The number of edges in a $k$-Helly hypergraph.  In Combinatorial mathematics (Marseille-Luminy, 1981), volume 75 of North-Holland Math. Stud., pages 497–501. North-Holland, Amsterdam, 1983.
  * [18] B. E. Sagan.  A note on independent sets in trees.  SIAM J. Discrete Math., 1(1):105–108, 1988.
  * [19] D. S. Taletskiĭ and D. S. Malyshev.  Trees without twin-leaves with the smallest number of maximal independent sets.  Diskret. Mat., 30(4):115–134, 2018.
  * [20] H. S. Wilf.  The number of maximal independent sets in a tree.  SIAM J. Algebraic Discrete Methods, 7(1):125–130, 1986.
  * [21] D. R. Wood.  On the number of maximal independent sets in a graph.  Discrete Math. Theor. Comput. Sci., 13(3):17–19, 2011.