# Number of facets of symmetric edge polytopes arising from
join graphs

Aki Mori, Kenta Mori and Hidefumi Ohsugi  Aki Mori, Learning center, Institute
for general education, Setsunan University, Neyagawa, Osaka, 572-8508, Japan
<EMAIL_ADDRESS>Kenta Mori, Department of Mathematical Sciences,
Graduate School of Science and Technology, Kwansei Gakuin University, Sanda,
Hyogo 669-1330, Japan<EMAIL_ADDRESS>Hidefumi Ohsugi, Department of
Mathematical Sciences, School of Science, Kwansei Gakuin University, Sanda,
Hyogo 669-1330, Japan<EMAIL_ADDRESS>
###### Abstract.

In the present paper, we study the upper and lower bounds for the number of
facets of symmetric edge polytopes of connected graphs conjectured by Braun
and Bruegge. In particular, we show that their conjecture is true for any
graph that is the join of two graphs (equivalently, for any connected graph
whose complement graph is not connected). It is known that any symmetric edge
polytope is a centrally symmetric reflexive polytope. Hence our results give a
partial answer to Nill’s conjecture: the number of facets of a $d$-dimensional
reflexive polytope is at most $6^{d/2}$.

###### Key words and phrases:

symmetric edge polytopes, number of facets, join graphs, reflexive polytopes

###### 2020 Mathematics Subject Classification:

52B20, 52B12

##  1\. Introduction

A lattice polytope ${\mathcal{P}}\subset{\mathbb{R}}^{d}$ is a convex polytope
all of whose vertices belong to ${\mathbb{Z}}^{d}$. A $d$-dimensional lattice
polytope ${\mathcal{P}}\subset{\mathbb{R}}^{d}$ is called reflexive if the
origin of ${\mathbb{R}}^{d}$ belongs to the interior of ${\mathcal{P}}$ and
its dual polytope

${\mathcal{P}}^{\vee}:=\\{{\mathbf{y}}\in{\mathbb{R}}^{d}:\langle{\mathbf{x}},{\mathbf{y}}\rangle\leq
1\ \text{for all}\ {\mathbf{x}}\in{\mathcal{P}}\\}$

is also a lattice polytope, where $\langle{\mathbf{x}},{\mathbf{y}}\rangle$ is
the usual inner product of ${\mathbb{R}}^{d}$. In general, we say that a
lattice polytope is reflexive if it is unimodularly equivalent to a reflexive
polytope. It is known [1] that reflexive polytopes correspond to Gorenstein
toric Fano varieties, and they are related to mirror symmetry. Let
$N({\mathcal{P}})$ be the number of facets of a lattice polytope
${\mathcal{P}}$. If ${\mathcal{P}}$ is reflexive, then $N({\mathcal{P}})$ is
the number of vertices of the reflexive polytope ${\mathcal{P}}^{\vee}$. The
number $N({\mathcal{P}})$ is important when ${\mathcal{P}}$ is a
$d$-dimensional reflexive polytope since $N({\mathcal{P}})-(d+1)$ is the rank
of the class group of the associated toric variety. Nill conjectured (a dual
version of) the following.

######  Conjecture 1.1 ([13, Conjecture 5.2]).

Let ${\mathcal{P}}$ be a $d$-dimensional reflexive polytope. Then
$N({\mathcal{P}})\leq 6^{d/2}$.

Nill [14] showed that Conjecture 1.1 is true for any pseudo-symmetric
reflexive simplicial $d$-dimensional polytope and the maximum $6^{d/2}$ is
attained if and only if $P$ is a free sum of $d/2$ copies of del Pezzo
polygons. On the other hand, Higashitani [9] showed that centrally symmetric
simplicial reflexive polytopes are precisely the “symmetric edge polytopes” of
graphs without even cycles. The definition of symmetric edge polytopes is as
follows. Let $G$ be a finite simple graph on the vertex set
$[n]:=\\{1,\ldots,n\\}$ with the edge set $E(G)$. The symmetric edge polytope
${\mathcal{P}}_{G}$ of $G$ is the convex hull of
$\\{\pm({\mathbf{e}}_{i}-{\mathbf{e}}_{j}):\\{i,j\\}\in E(G)\\},$ where
${\mathbf{e}}_{i}$ is the $i$-th unit coordinate vector in ${\mathbb{R}}^{n}$.
It is known that the symmetric edge polytope of a connected graph with $n$
vertices is a centrally symmetric reflexive $(n-1)$-dimensional polytope.
Symmetric edge polytopes are studied in several different areas. The name
“symmetric edge polytope” was given in [12] in the study of Ehrhart theory.
Symmetric edge polytopes are known as adjacency polytopes ([5]) which have an
application to Kuramoto models. A partial list of papers which include the
results on symmetric edge polytopes is [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
15, 16]. In particular the facets of symmetric edge polytopes are very
important and studied in many papers (see, e.g., [2, 3, 4, 6, 10, 11]).

Braun and Bruegge [2] conjectured upper and lower bounds for the number of the
facets of symmetric edge polytopes. Let $G_{1}$ and $G_{2}$ be graphs with
exactly one common vertex. Then the $1$-sum (called wedge in [2]) of $G_{1}$
and $G_{2}$ is the union of $G_{1}$ and $G_{2}$. The $1$-sum of several graphs
are defined by a sequence of $1$-sums. It is known [2] that
$N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})$ if $G$
is the $1$-sum of $G_{1}$ and $G_{2}$. Let $K_{n}$ denote the complete graph
with $n$ vertices, and let $K_{\ell_{1},\dots,\ell_{s}}$ denote the complete
multipartite graph on the vertex set $V_{1}\sqcup\dots\sqcup V_{s}$ with
$|V_{i}|=\ell_{i}$. It is known [10] that
$N({\mathcal{P}}_{K_{\ell,m}})=2^{\ell}+2^{m}-2$ and
$N({\mathcal{P}}_{K_{\ell_{1},\dots,\ell_{s}}})=2^{\sum_{i=1}^{s}\ell_{i}}-\sum_{i=1}^{s}(2^{\ell_{i}}-2)-2$
if $s\geq 3$. In particular, we have $N({\mathcal{P}}_{K_{n}})=2^{n}-2$. Braun
and Bruegge [2] conjectured the following, and studied $N({\mathcal{P}}_{G})$
for sparse graphs $G$. (Note that $2^{\frac{n}{2}+1}-2<3\cdot
2^{\frac{n-1}{2}}-2$ and $14\cdot 6^{\frac{n}{2}-2}<6^{\frac{n-1}{2}}$ for any
$n\in\mathbb{N}$.)

######  Conjecture 1.2 ([2, Conjecture 2]).

Let $G$ be a connected graph with $n\geq 3$ vertices.

  * (1)

If $n$ is odd, then we have $3\cdot 2^{\frac{n-1}{2}}-2\leq
N({\mathcal{P}}_{G})\leq 6^{\frac{n-1}{2}}$. In addition,

    * $\cdot$

$N({\mathcal{P}}_{G})=3\cdot 2^{\frac{n-1}{2}}-2$ if and only if
$G=K_{(n-1)/2,(n+1)/2}$.

    * $\cdot$

$N({\mathcal{P}}_{G})=6^{\frac{n-1}{2}}$ if and only if $G$ is the $1$-sum of
$(n-1)/2$ triangles.

  * (2)

If $n$ is even, then we have $2^{\frac{n}{2}+1}-2\leq N({\mathcal{P}}_{G})\leq
14\cdot 6^{\frac{n}{2}-2}$. In addition,

    * $\cdot$

$N({\mathcal{P}}_{G})=2^{\frac{n}{2}+1}-2$ if and only if $G=K_{n/2,n/2}$.

    * $\cdot$

$N({\mathcal{P}}_{G})=14\cdot 6^{\frac{n}{2}-2}$ if and only if $G$ is the
$1$-sum of $K_{4}$ with $n/2-2$ triangles.

Let $G=(V,E)$ be a graph on the vertex set $V=[n-1]$. Then the suspension
${\widehat{G}}$ of $G$ is the graph on the vertex set $[n]$ and the edge set
$E\cup\\{\\{i,n\\}:i\in[n-1]\\}$. In the present paper, we show that
Conjecture 1.2 is true for any suspension graph.

######  Theorem 1.3.

Let $G$ be a graph on the vertex set $[n-1]$ with $n\geq 2$. Then

$N({\mathcal{P}}_{{\widehat{G}}})\geq 2^{n-1}$

and equality holds if and only if $G$ is an empty graph (i.e., a graph having
no edges), and hence ${\widehat{G}}$ is a star graph $K_{1,n-1}$. Moreover,

$N({\mathcal{P}}_{{\widehat{G}}})\leq\begin{cases}6^{\frac{n-1}{2}}&\mbox{if
}n\mbox{ is odd,}\\\ 14\cdot 6^{\frac{n}{2}-2}&\mbox{if }n\mbox{ is
even}\end{cases}$

and equality holds if and only if one of the following holds:

  * (a)

$n$ is odd, and $G$ is a disjoint union of $(n-1)/2$ edges, and hence
${\widehat{G}}$ is a $1$-sum of $(n-1)/2$ triangles.

  * (b)

$n$ is even, and $G$ is a disjoint union of $n/2-2$ edges with a triangle, and
hence ${\widehat{G}}$ is a $1$-sum of $K_{4}$ with $n/2-2$ triangles.

In addition, we extend Theorem 1.3 to the join of two graphs. Let
$G_{1}=(V,E)$ and $G_{2}=(V^{\prime},E^{\prime})$ be (not necessarily
connected) graphs with $V\cap V^{\prime}=\emptyset$. Then the join
$G_{1}+G_{2}$ of $G_{1}$ and $G_{2}$ is the graph on the vertex set $V\cup
V^{\prime}$ and the edge set $E\cup E^{\prime}\cup\\{\\{i,j\\}:i\in V,j\in
V^{\prime}\\}$. For example, $K_{\ell}+K_{m}=K_{\ell+m}$ and the join of two
empty graphs is a complete bipartite graph. Note that $K_{1}+G$ is the
suspension of $G$. By the following theorem, Conjecture 1.2 holds for any
connected graph whose complement is not connected.

######  Theorem 1.4.

Let $G_{1}=(V,E)$ and $G_{2}=(V^{\prime},E^{\prime})$ be graphs with $V\cap
V^{\prime}=\emptyset$ and let $n=|V|+|V^{\prime}|$. Then

$3\cdot 2^{\frac{n-1}{2}}-2\leq N({\mathcal{P}}_{G_{1}+G_{2}})\leq
6^{\frac{n-1}{2}}$

if $n$ is odd, and

$2^{\frac{n}{2}+1}-2\leq N({\mathcal{P}}_{G_{1}+G_{2}})\leq 14\cdot
6^{\frac{n}{2}-2}$

if $n$ is even.

The present paper is organized as follows. In Section 2, after reviewing the
characterizations of the facets of symmetric edge polytopes, we confirm that,
in order to study Conjecture 1.2, it is enough to consider 2-connected
nonbipartite graphs. Next, in Section 3, using a characterization of the
facets of symmetric edge polytopes of suspension graphs, we give a proof of
Theorem 1.3. Finally, in Section 4, we extend Theorem 1.3 to join graphs by
giving a proof of Theorem 1.4. From the results in the present paper, in order
to study Conjecture 1.2, it is enough to discuss $2$-connected non-bipartite
graphs whose complement is connected.

##  2\. Basics on the facets of symmetric edge polytopes

In the present section, we will give some basic results on the facets of
symmetric edge polytopes. First, we review the characterizations of facets of
symmetric edge polytopes.

######  Proposition 2.1 ([10, Theorem 3.1]).

Let $G=(V,E)$ be a connected graph. Then $f:V\rightarrow{\mathbb{Z}}$ defines
a facet of ${\mathcal{P}}_{G}$ if and only if both of the following hold.

  * (i)

For every edge $e=\\{i,j\\}$, we have $|f(i)-f(j)|\leq 1$.

  * (ii)

The subset of edges $E_{f}:=\\{e=\\{i,j\\}\in E:|f(u)-f(v)|=1\\}$ forms a
spanning connected subgraph of $G$.

There exists a characterization for the subgraphs appearing in Proposition
2.1.

######  Definition 2.2.

If $f:V\rightarrow{\mathbb{Z}}$ defines a facet of ${\mathcal{P}}_{G}$, then
the graph $G_{f}:=(V,E_{f})$ in Proposition 2.1 is called the facet subgraph
of $G$ associated with $f$. Let ${\rm FS}(G)$ denote the set of all facet
subgraphs of $G$. Given a facet subgraph $H\in{\rm FS}(G)$, let $\mu(H)$
denote the number of facets of ${\mathcal{P}}_{G}$ whose facet subgraph is
$H$.

Note that, if $G$ is bipartite, then ${\rm FS}(G)=\\{G\\}$. The following fact
is often used in the study of $N({\mathcal{P}}_{G})$.

######  Proposition 2.3.

Let $G$ be a connected graph. Then

$N({\mathcal{P}}_{G})=\sum_{H\in{\rm FS}(G)}\mu(H).$

On the other hand, a characterization of facet subgraphs of $G$ is known. A
spanning subgraph of $G$ is a subgraph of $G$ which contains every vertex of
$G$.

######  Proposition 2.4 ([4, Theorem 3 (2)]).

Let $G$ be a connected graph. A subgraph $H$ of $G$ is a facet subgraph of $G$
if and only if it is a maximal connected spanning bipartite subgraph of $G$.

The following upper bound for bipartite graphs is known.

######  Proposition 2.5 ([6, Corollary 33]).

Let $G$ be a connected bipartite graph with $n$ vertices. Then
$N({\mathcal{P}}_{G})\leq 2^{n-1}$, and the equality holds if $G$ is a tree.

Note that $2^{n-1}<14\cdot 6^{\frac{n}{2}-2}$ for any $n\geq 2$. Since we
cannot find it in literature, we confirm that the lower bound in Conjecture
1.2 is true for bipartite graphs by using the following proposition.

######  Proposition 2.6.

Let $G=(V,E)$ be a connected bipartite graph. Suppose that the bipartite graph
$G-e$ on the vertex set $V$ obtained from $G$ by deleting an edge $e$ of $G$
is connected. Then we have $N({\mathcal{P}}_{G})\leq N({\mathcal{P}}_{G-e})$.

###### Proof.

From Proposition 2.1, $f:V\rightarrow{\mathbb{Z}}$ defines a facet of
${\mathcal{P}}_{G-e}$ if $f:V\rightarrow{\mathbb{Z}}$ defines a facet of
${\mathcal{P}}_{G}$. Thus we have $N({\mathcal{P}}_{G})\leq
N({\mathcal{P}}_{G-e})$. ∎

We now show that the lower bound in Conjecture 1.2 is true for bipartite
graphs.

######  Proposition 2.7.

Let $G$ be a connected bipartite graph with $n$ vertices.

  * (a)

If $n$ is odd, then we have $N({\mathcal{P}}_{G})\geq 3\cdot
2^{\frac{n-1}{2}}-2$, and the equality holds if and only if
$G=K_{(n-1)/2,(n+1)/2}$.

  * (b)

If $n$ is even, then we have $N({\mathcal{P}}_{G})\geq 2^{\frac{n}{2}+1}-2$,
and the equality holds if and only if $G=K_{n/2,n/2}$.

###### Proof.

Let $G$ be a connected bipartite graph on the vertex set $V=V_{1}\sqcup
V_{2}$, where $n_{1}=|V_{1}|$ and $n_{2}=|V_{2}|$ with $n_{1}\leq n_{2}$.
Using Proposition 2.6 repeatedly from $K_{n_{1},n_{2}}$ to $G$, we have

$N({\mathcal{P}}_{G})\geq
N({\mathcal{P}}_{K_{n_{1},n_{2}}})=2^{n_{1}}+2^{n_{2}}-2.$

On the other hand,

$2^{n_{1}}+2^{n_{2}}\geq\left\\{\begin{array}[]{cc}2^{\frac{n}{2}}+2^{\frac{n}{2}}=2^{\frac{n}{2}+1}&\mbox{if
}n\mbox{ is even,}\\\ 2^{\frac{n-1}{2}}+2^{\frac{n+1}{2}}=3\cdot
2^{\frac{n-1}{2}}&\mbox{if }n\mbox{ is odd.}\end{array}\right.$

Equality holds when $n/2=n_{1}=n_{2}$ if $n$ is even, and $n_{1}=(n-1)/2$ and
$n_{2}=(n+1)/2$ if $n$ is odd. ∎

We close the present section by proving that a connected graph $G$ satisfies
the condition of Conjecture 1.2 if each “block” of $G$ satisfies the condition
of Conjecture 1.2. Blocks of a graph are defined as follows.

######  Definition 2.8.

Let $G$ be a connected graph. A vertex $v$ of $G$ is called a cut vertex if
the graph obtained by the removal of $v$ from $G$ is disconnected. A block of
$G$ is a maximal connected subgraph of $G$ without cut vertices.

In particular, any connected graph is the $1$-sum of its blocks.

######  Proposition 2.9 ([2, Proposition 9]).

Let $G$ be the $1$-sum of connected graphs $G_{1}$ and $G_{2}$. Then we have
$N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})$.

From this proposition, we have the following.

######  Proposition 2.10.

Let $G$ be the $1$-sum of connected graphs $G_{1}$ and $G_{2}$. If $G_{1}$ and
$G_{2}$ satisfy the condition of Conjecture 1.2, then so does $G$.

###### Proof.

Let $n_{i}\geq 2$ be the number of vertices of $G_{i}$ for $i=1,2$. Then $G$
has $n=n_{1}+n_{2}-1$ vertices.

Case 1 (both $n_{1}$ and $n_{2}$ are odd). Then $n$ is odd. From Proposition
2.9,

$N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})\leq
6^{\frac{n_{1}-1}{2}}\cdot 6^{\frac{n_{2}-1}{2}}=6^{\frac{n-1}{2}}$

and

$\displaystyle
N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})$
$\displaystyle\geq$ $\displaystyle\left(3\cdot
2^{\frac{n_{1}-1}{2}}-2\right)\left(3\cdot 2^{\frac{n_{2}-1}{2}}-2\right)$
$\displaystyle=$ $\displaystyle 3\cdot
2^{\frac{n-1}{2}}-2+6\left(2^{\frac{n_{1}-1}{2}}-1\right)\left(2^{\frac{n_{2}-1}{2}}-1\right)$
$\displaystyle>$ $\displaystyle 3\cdot 2^{\frac{n-1}{2}}-2.$

Case 2 (both $n_{1}$ and $n_{2}$ are even). Then $n$ is odd. From Proposition
2.9,

$N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})\leq
14\cdot 6^{\frac{n_{1}}{2}-2}\cdot 14\cdot
6^{\frac{n_{2}}{2}-2}=\frac{49}{54}\cdot 6^{\frac{n-1}{2}}<6^{\frac{n-1}{2}}$

and

$\displaystyle
N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})$
$\displaystyle\geq$
$\displaystyle\left(2^{\frac{n_{1}}{2}+1}-2\right)\left(2^{\frac{n_{2}}{2}+1}-2\right)$
$\displaystyle=$ $\displaystyle 3\cdot
2^{\frac{n-1}{2}}-2+2\left(2^{\frac{n_{1}}{2}}-2\right)\left(2^{\frac{n_{2}}{2}}-2\right)+2^{\frac{n-1}{2}}-2$
$\displaystyle\geq$ $\displaystyle 3\cdot 2^{\frac{n-1}{2}}-2.$

(In the last inequality, equality holds if and only if $n_{1}=n_{2}=2$ and
hence $G=K_{1,2}$.)

Case 3 ($n_{1}$ is odd and $n_{2}$ is even). Then $n$ is even. From
Proposition 2.9,

$N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})\leq
6^{\frac{n_{1}-1}{2}}\cdot 14\cdot 6^{\frac{n_{2}}{2}-2}=14\cdot
6^{\frac{n}{2}-2}$

and

$\displaystyle
N({\mathcal{P}}_{G})=N({\mathcal{P}}_{G_{1}})N({\mathcal{P}}_{G_{2}})$
$\displaystyle\geq$ $\displaystyle\left(3\cdot
2^{\frac{n_{1}-1}{2}}-2\right)\left(2^{\frac{n_{2}}{2}+1}-2\right)$
$\displaystyle=$ $\displaystyle
2^{\frac{n}{2}+1}-2+2\left(2^{\frac{n_{1}-1}{2}}-1\right)\left(2^{\frac{n_{2}}{2}+1}-3\right)$
$\displaystyle>$ $\displaystyle 2^{\frac{n}{2}+1}-2,$

as desired. ∎

As explained in Introduction, it is known that
$N({\mathcal{P}}_{K_{\ell_{1},\dots,\ell_{s}}})=2^{\sum_{i=1}^{s}\ell_{i}}-\sum_{i=1}^{s}(2^{\ell_{i}}-2)-2$
if $s\geq 3$. Thus Conjecture 1.2 is true for complete multipartite graphs.
Since every 2-connected graph with $n\leq 4$ vertices is complete
multipartite, we have the following from Proposition 2.10.

######  Proposition 2.11.

Conjecture 1.2 is true for $n=3,4$.

##  3\. Facets of symmetric edge polytopes of suspension graphs

In the present section, using a characterization of the facets of symmetric
edge polytopes of suspension graphs, we give a proof of Theorem 1.3.

######  Definition 3.1.

Let $G$ be a graph on the vertex set $V$. Given a vertex $v$ of $G$, let
$N_{G}(v)$ denote the set of all vertices that are adjacent to $v$ in $G$. Let
$N_{G}[v]:=N_{G}(v)\cup\\{v\\}$. A subset $S\subset V$ is called a dominating
set of $G$ if $\bigcup_{v\in S}N_{G}[v]=V$.

Note that if $S\subset V$ is a dominating set of $G$, then any
$S^{\prime}\subset V$ with $S\subset S^{\prime}$ is a dominating set of $G$.
Facet subgraphs of a suspension graph is characterized by dominating sets.

######  Lemma 3.2.

Let $G$ be a graph on the vertex set $[n-1]$, and let $H$ be a maximal
spanning bipartite subgraph of ${\widehat{G}}$ on the vertex set
$[n]=V_{1}\sqcup V_{2}$, where $n\in V_{1}$. Then $H$ is a facet subgraph of
${\widehat{G}}$ if and only if $V_{2}$ is a dominating set of $G$.

###### Proof.

Since $H$ is a maximal spanning bipartite subgraph of ${\widehat{G}}$, $H$ is
a facet subgraph of ${\widehat{G}}$ if and only if $H$ is connected. Since
$n\in V_{1}$ is adjacent to any vertex in $V_{2}$, $H$ is connected if and
only if $V_{2}$ is a dominating set of $G$. ∎

######  Definition 3.3.

Let $G$ be a graph on the vertex set $V$. Then let $c(G)$ denote the number of
connected components of $G$. Given a subset $S\subset V$, let $G[S]$ denote
the induced subgraph of $G$ on the vertex set $S$.

######  Lemma 3.4.

Let $G$ be a graph on the vertex set $[n-1]$. Suppose that $H$ is a facet
subgraph of ${\widehat{G}}$ on the vertex set $[n]=V_{1}\sqcup V_{2}$, where
$n\in V_{1}$. Then we have $\mu(H)=2^{c(G[V_{2}])}$.

###### Proof.

Suppose that $H$ is the facet subgraph for a facet defined by
$f:[n]\rightarrow{\mathbb{Z}}$. We may assume that $f(n)=0$. For each $i\in
V_{1}$, since $\\{i,n\\}$ is an edge of $\widehat{G}$ and not an edge of $H$,
we have $f(i)=0$ from Proposition 2.1. Since $H$ is a facet subgraph of $f$,
it follows that $|f(j)|=1$ for each $j\in V_{2}$. If $j_{1},j_{2}\in V_{2}$
belong to the same connected component of $G[V_{2}]$, then
$f(j_{1})=f(j_{2})$. If $j_{1},j_{2}\in V_{2}$ do not belong to the same
connected component of $G[V_{2}]$, then $f(j_{1})$ and $f(j_{2})$ are
independent. Thus one can choose $1$ or $-1$ for the value of $f$ for each
connected component of $G[V_{2}]$. ∎

######  Definition 3.5.

Given a vertex $v$ of a graph $G=(V,E)$, we define the following three graphs:

  * •

Let $G-v$ denote the induced subgraph $G[V\setminus\\{v\\}]$ of $G$;

  * •

If $N_{G}[v]\neq V$, then let $G-N_{G}[v]$ denote the induced subgraph
$G[V\setminus N_{G}[v]]$ of $G$;

  * •

Let $G/v$ denote the graph obtained from $G$ by removal of $v$ and insertion
of all edges $\\{i,j\\}$ such that $i,j\in N_{G}(v)$.

######  Proposition 3.6.

Let $G$ be a graph on the vertex set $[n-1]$ with $n\geq 3$. Given a vertex
$v$ of $G$, we have

(1) $N({\mathcal{P}}_{\widehat{G-v}})+N({\mathcal{P}}_{\widehat{G/v}})\ \
\leq\ \ N({\mathcal{P}}_{\widehat{G}})\ \ \leq\ \
N({\mathcal{P}}_{\widehat{G-v}})+2N({\mathcal{P}}_{\widehat{G-N_{G}[v]}})+N({\mathcal{P}}_{\widehat{G/v}})$

if $N_{G}[v]\neq[n-1]$, and

(2) $N({\mathcal{P}}_{\widehat{G}})\ \ =\ \
N({\mathcal{P}}_{\widehat{G-v}})+N({\mathcal{P}}_{\widehat{G/v}})+2$

if $N_{G}[v]=[n-1]$.

###### Proof.

We define partitions

$\displaystyle{\rm FS}(\widehat{G})$ $\displaystyle=$ $\displaystyle{\rm
FS}_{0}(\widehat{G})\sqcup{\rm FS}_{1}(\widehat{G})\sqcup{\rm
FS}_{2}(\widehat{G}),$ $\displaystyle{\rm FS}(\widehat{G-v})$ $\displaystyle=$
$\displaystyle{\rm FS}_{1}(\widehat{G-v})\sqcup{\rm FS}_{2}(\widehat{G-v}),$
$\displaystyle{\rm FS}(\widehat{G/v})$ $\displaystyle=$ $\displaystyle{\rm
FS}_{1}(\widehat{G/v})\sqcup{\rm FS}_{2}(\widehat{G/v}),$

where

$\displaystyle{\rm FS}_{0}(\widehat{G})$ $\displaystyle:=$
$\displaystyle\left\\{H\in{\rm FS}({\widehat{G}}):\begin{array}[]{c}\mbox{the
bipartition of }H\mbox{ is }V_{1}\sqcup V_{2},\mbox{ where }n\in V_{1},\\\ \
\mbox{ and }v\in V_{1}\end{array}\right\\},$ $\displaystyle{\rm
FS}_{1}(\widehat{G})$ $\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}({\widehat{G}}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }n\in V_{1},\\\ \ v\in V_{2}\mbox{ and
}N_{G}(v)\subset V_{1}\end{array}\right\\},$ $\displaystyle{\rm
FS}_{2}(\widehat{G})$ $\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}({\widehat{G}}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }n\in V_{1},\\\ v\in V_{2},\mbox{ and
}N_{G}(v)\cap V_{2}\neq\emptyset\end{array}\right\\},$ $\displaystyle{\rm
FS}_{1}(\widehat{G-v})$ $\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}(\widehat{G-v}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }n\in V_{1},\\\ \mbox{and }N_{G}(v)\subset
V_{1}\end{array}\right\\},$ $\displaystyle{\rm FS}_{2}(\widehat{G-v})$
$\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}(\widehat{G-v}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }n\in V_{1},\\\ \mbox{and }N_{G}(v)\cap
V_{2}\neq\emptyset\end{array}\right\\},$ $\displaystyle{\rm
FS}_{1}(\widehat{G/v})$ $\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}(\widehat{G/v}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }n\in V_{1},\\\ \mbox{and }N_{G}(v)\subset
V_{1}\end{array}\right\\},$ $\displaystyle{\rm FS}_{2}(\widehat{G/v})$
$\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}(\widehat{G/v}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }n\in V_{1},\\\ \mbox{and }N_{G}(v)\cap
V_{2}\neq\emptyset\end{array}\right\\}.$

First, we will show the second inequality in (1).

Claim 1. $\varphi:{\rm FS}_{0}({\widehat{G}})\rightarrow{\rm
FS}_{2}(\widehat{G-v})$, $H\mapsto H-v$ is a bijection such that
$\mu(H)=\mu(\varphi(H))$.

Let $H\in{\rm FS}_{0}({\widehat{G}})$. Since $V_{2}$ is a dominating set of
$G$ and since $v\in V_{1}$, it follows that $V_{2}$ is a dominating set of
$G-v$, and that $N_{G}(v)\cap V_{2}\neq\emptyset$. Hence $H-v\in{\rm
FS}_{2}(\widehat{G-v})$. Since $G[V_{2}]=(G-v)[V_{2}]$, we have
$c(G[V_{2}])=c((G-v)[V_{2}])$. From Lemma 3.4,
$\mu(H)=\mu(H-v)=2^{c(G[V_{2}])}$.

Conversely, let $H_{1}\in{\rm FS}_{2}(\widehat{G-v})$. Since $V_{2}$ is a
dominating set of $G-v$ and since $N_{G}(v)\cap V_{2}\neq\emptyset$, $V_{2}$
is a dominating set of $G$. Hence the bipartite graph $H$ obtained from
$H_{1}$ by adding the vertex $v$ to $V_{1}$ and edges $\\{v,v^{\prime}\\}$
($v^{\prime}\in N_{G}(v)\cap V_{2}$) is a facet subgraph of ${\widehat{G}}$
with $\varphi(H)=H_{1}$.

Claim 2. $\varphi:{\rm FS}_{2}({\widehat{G}})\rightarrow{\rm
FS}_{2}(\widehat{G/v})$, $H\mapsto\widetilde{H}$ defined below is a bijection
such that $\mu(H)=\mu(\varphi(H))$.

Let $H\in{\rm FS}_{2}({\widehat{G}})$. Since $V_{2}$ is a dominating set of
$G$ and since $N_{G}(v)\cap V_{2}\neq\emptyset$, it follows that
$V_{2}\setminus\\{v\\}$ is a dominating set of $G/v$. Hence the maximal
spanning bipartite subgraph $\widetilde{H}$ of $\widehat{G/v}$ on the vertex
set $V_{1}\sqcup(V_{2}\setminus\\{v\\})$ is a facet subgraph of
$\widehat{G/v}$. Since $N_{G}(v)\cap V_{2}\neq\emptyset$, we have
$\widetilde{H}\in{\rm FS}_{2}(\widehat{G/v})$ and
$c(G[V_{2}])=c((G/v)[V_{2}\setminus\\{v\\}])$. From Lemma 3.4,
$\mu(H)=\mu(\widetilde{H})=2^{c(G[V_{2}])}$.

Conversely, let $H_{2}\in{\rm FS}_{2}(\widehat{G/v})$. Since $V_{2}$ is a
dominating set of $G/v$, $V_{2}\cup\\{v\\}$ is a dominating set of $G$. Hence
the maximal spanning bipartite subgraph $H$ of ${\widehat{G}}$ on the vertex
set $V_{1}\sqcup(V_{2}\cup\\{v\\})$ is a facet subgraph of ${\widehat{G}}$
such that $\varphi(H)=H_{2}$.

Claim 3. If $N_{G}[v]\neq[n-1]$, then $\varphi:{\rm
FS}_{1}({\widehat{G}})\rightarrow{\rm FS}(\widehat{G-N_{G}[v]})$, $H\mapsto
H-N_{G}[v]$ is an injection such that $\mu(H)=2\mu(\varphi(H))$.

Let $H\in{\rm FS}_{1}({\widehat{G}})$. Since $V_{2}$ is a dominating set of
$G$ and since $N_{G}(v)\subset V_{1}$, it follows that $V_{2}\setminus\\{v\\}$
is a dominating set of $G-N_{G}[v]$. Hence $H-N_{G}[v]\in{\rm
FS}(\widehat{G-N_{G}[v]})$. Since $G[V_{2}]$ is the union of
$(G-N_{G}[v])[V_{2}\setminus\\{v\\}]$ and the isolated vertex $v$, we have
$c(G[V_{2}])=c((G-N_{G}[v])[V_{2}\setminus\\{v\\}])+1$. From Lemma 3.4,
$\mu(H-N_{G}[v])=2^{c(G[V_{2}])-1}=\mu(H)/2$.

From Claims 1, 2, and 3 above, we have

$\displaystyle N({\mathcal{P}}_{\widehat{G}})$ $\displaystyle=\sum_{H\in{\rm
FS}_{0}({\widehat{G}})}\mu(H)+\sum_{H\in{\rm
FS}_{1}({\widehat{G}})}\mu(H)+\sum_{H\in{\rm FS}_{2}({\widehat{G}})}\mu(H)$
$\displaystyle\leq\sum_{H\in{\rm FS}(\widehat{G-v})}\mu(H)+\sum_{H\in{\rm
FS}(\widehat{G-N_{G}[v]})}2\mu(H)+\sum_{H\in{\rm FS}(\widehat{G/v})}\mu(H)$
$\displaystyle=N({\mathcal{P}}_{\widehat{G-v}})+2N({\mathcal{P}}_{\widehat{G-N_{G}[v]}})+N({\mathcal{P}}_{\widehat{G/v}}).$

Next, we will show the first inequality in (1).

Claim 4. There is an injection $\varphi:{\rm
FS}_{1}(\widehat{G-v})\rightarrow{\rm FS}_{1}({\widehat{G}})$ such that
$\mu(H_{1})=\mu(\varphi(H_{1}))/2$.

Let $H_{1}\in{\rm FS}_{1}(\widehat{G-v})$. Since $V_{2}$ is a dominating set
of $G-v$, $V_{2}\cup\\{v\\}$ is a dominating set of $G$. Hence the bipartite
graph $H$ obtained from $H_{1}$ by adding the vertex $v$ to $V_{2}$ and edges
$\\{v,v^{\prime}\\}$ ($v^{\prime}\in N_{G}(v)$) is a facet subgraph of
${\widehat{G}}$. Since $G[V_{2}\cup\\{v\\}]$ is the union of $(G-v)[V_{2}]$
and the isolated vertex $v$, we have
$c(G[V_{2}\cup\\{v\\}])=c((G-v)[V_{2}])+1$. From Lemma 3.4,
$\mu(H)=2^{c((G-v)[V_{2}])+1}=2\mu(H_{1})$.

Claim 5. There is an injection $\varphi:{\rm
FS}_{1}(\widehat{G/v})\rightarrow{\rm FS}_{1}({\widehat{G}})$ such that
$\mu(H_{2})=\mu(\varphi(H_{2}))/2$.

Let $H_{2}\in{\rm FS}_{1}(\widehat{G/v})$. Since $V_{2}$ is a dominating set
of $G/v$, $V_{2}\cup\\{v\\}$ is a dominating set of $G$. Hence the maximal
spanning bipartite subgraph $H$ of ${\widehat{G}}$ on the vertex set
$V_{1}\sqcup(V_{2}\cup\\{v\\})$ is a facet subgraph of ${\widehat{G}}$. Since
$G[V_{2}\cup\\{v\\}]$ is the union of $(G/v)[V_{2}]$ and the isolated vertex
$v$, we have $c(G[V_{2}\cup\\{v\\}])=c((G/v)[V_{2}])+1$. From Lemma 3.4,
$\mu(H)=2^{c((G/v)[V_{2}])+1}=2\mu(H_{2})$.

From Claims 1, 2, 4, and 5, we have

$\displaystyle
N({\mathcal{P}}_{\widehat{G-v}})+N({\mathcal{P}}_{\widehat{G/v}})$
$\displaystyle=\sum_{H\in{\rm FS}_{1}(\widehat{G-v})}\mu(H)+\sum_{H\in{\rm
FS}_{2}(\widehat{G-v})}\mu(H)+\sum_{H\in{\rm
FS}_{1}(\widehat{G/v})}\mu(H)+\sum_{H\in{\rm FS}_{2}(\widehat{G/v})}\mu(H)$
$\displaystyle\leq\sum_{H\in{\rm
FS}_{1}(\widehat{G})}\frac{1}{2}\mu(H)+\sum_{H\in{\rm
FS}_{0}(\widehat{G})}\mu(H)+\sum_{H\in{\rm
FS}_{1}(\widehat{G})}\frac{1}{2}\mu(H)+\sum_{H\in{\rm
FS}_{2}(\widehat{G})}\mu(H)$ $\displaystyle=N({\mathcal{P}}_{\widehat{G}}).$

Finally , we will show (2). Suppose that $N_{G}[v]=[n-1]$. Then

Claim 6. ${\rm FS}_{1}({\widehat{G}})=\\{H_{0}\\}$ where $H_{0}$ is a star
graph and $\mu(H_{0})=2$.

Suppose that $H_{0}\in{\rm FS}_{1}({\widehat{G}})$. Since $N_{G}[v]=[n-1]$,
$V_{1}=[n]\setminus\\{v\\}$ and $V_{2}=\\{v\\}$. Hence $H_{0}$ is the star
graph with the edge set $\\{\\{i,v\\}:v\neq i\in[n]\\}$ and $\mu(H_{0})=2$.
Conversely if $H_{0}$ is the star graph with the edge set $\\{\\{i,v\\}:v\neq
i\in[n]\\}$, then $H_{0}$ belongs to ${\rm FS}_{1}({\widehat{G}})$.

Since $N_{G}[v]=[n-1]$, we have ${\rm FS}_{1}(\widehat{G-v})={\rm
FS}_{1}(\widehat{G/v})=\emptyset$. From Claims 1, 2, and 6, we have

$\displaystyle N({\mathcal{P}}_{\widehat{G}})$ $\displaystyle=\sum_{H\in{\rm
FS}_{0}(\widehat{G})}\mu(H)+\sum_{H\in{\rm
FS}_{2}(\widehat{G})}\mu(H)+\mu(H_{0})$ $\displaystyle=\sum_{H\in{\rm
FS}_{2}(\widehat{G-v})}\mu(H)+\sum_{H\in{\rm FS}_{2}(\widehat{G/v})}\mu(H)+2$
$\displaystyle=N({\mathcal{P}}_{\widehat{G-v}})+N({\mathcal{P}}_{\widehat{G/v}})+2,$

as desired. ∎

######  Corollary 3.7.

Let $G$ be a graph with $n-1\geq 2$ vertices. Then

$N({\mathcal{P}}_{\widehat{\widehat{G\;}}})=N({\mathcal{P}}_{\widehat{G}})+2^{n}.$

###### Proof.

Note that $\widehat{G}$ has a vertex $v$ of degree $n-1$. Then
$\widehat{G}-v=G$ and $\widehat{G}/v=K_{n-1}$. From Proposition 3.6 (2), we
have

$N({\mathcal{P}}_{\widehat{\widehat{G\;}}})=N({\mathcal{P}}_{\widehat{G}})+N({\mathcal{P}}_{\widehat{K_{n-1}}})+2=N({\mathcal{P}}_{\widehat{G}})+(2^{n}-2)+2=N({\mathcal{P}}_{\widehat{G}})+2^{n}.$

∎

We are in a position to prove Theorem 1.3.

###### Proof of Theorem 1.3.

Proof is by induction on $n$ ($\geq 2$). If $n=2$, then ${\widehat{G}}=K_{2}$
and hence

$2^{1}=N({\mathcal{P}}_{\widehat{G}})<14\cdot 6^{-1}.$

Thus the assertion holds. Suppose that $n>2$ and the assertion is true for the
graphs with less number of vertices.

Case 1 ($G$ has no vertices of degree $\geq 2$). Then $G$ is a disjoint union
of edges $e_{1},\dots,e_{t}$ and isolated vertices $v_{1},\dots,v_{n-2t-1}$.
The suspension ${\widehat{G}}$ of $G$ is a $1$-sum of $t$ triangles together
with $n-2t-1$ edges. Since $N({\mathcal{P}}_{K_{2}})=2$ and
$N({\mathcal{P}}_{K_{3}})=6$, we have

$N({\mathcal{P}}_{{\widehat{G}}})=2^{n-2t-1}\cdot
6^{t}=\left(\frac{2}{3}\right)^{\frac{n-2t-1}{2}}6^{\frac{n-1}{2}}\leq
6^{\frac{n-1}{2}}.$

The equality holds if and only if $n-2t-1=0$, that is, ${\widehat{G}}$ is a
$1$-sum of $t$ triangles. Note that $n$ is odd if $n-2t-1=0$. Suppose that $n$
($\geq 4$) is even. Then $n-2t-1\geq 1$. Hence

$\left(\frac{2}{3}\right)^{\frac{n-2t-1}{2}}6^{\frac{n-1}{2}}\leq\left(\frac{2}{3}\right)^{\frac{1}{2}}6^{\frac{n-1}{2}}=12\cdot
6^{\frac{n}{2}-2}<14\cdot 6^{\frac{n}{2}-2}.$

On the other hand,

$N({\mathcal{P}}_{{\widehat{G}}})=2^{n-2t-1}\cdot
6^{t}=\left(\frac{3}{2}\right)^{t}2^{n-1}\geq 2^{n-1},$

and equality holds if and only if $t=0$, that is, $G$ is an empty graph.

Case 2 ($G$ has a vertex $v$ of degree $\geq 2$). Then $n\geq 4$. Since
$\deg(v)\geq 2$, $G/v$ is not empty. By the hypothesis of induction,

$\begin{array}[]{cclccc}2^{n-2}&\leq&N({\mathcal{P}}_{\widehat{G-v}})&\leq&6^{\frac{n-2}{2}},&\\\
2^{n-2}&<&N({\mathcal{P}}_{\widehat{G/v}})&\leq&6^{\frac{n-2}{2}},&\\\
&&N({\mathcal{P}}_{\widehat{G-N_{G}[v]}})&\leq&6^{\frac{n-4}{2}}&(\mbox{if
}N_{G}[v]\neq[n-1]).\end{array}$

Case 2.1 ($N_{G}[v]=[n-1]$). From Proposition 3.6 (2), we have

$\displaystyle N({\mathcal{P}}_{\widehat{G}})$
$\displaystyle=N({\mathcal{P}}_{\widehat{G-v}})+N({\mathcal{P}}_{\widehat{G/v}})+2>2^{n-2}+2^{n-2}+2>2^{n-1},$
$\displaystyle N({\mathcal{P}}_{\widehat{G}})$
$\displaystyle=N({\mathcal{P}}_{\widehat{G-v}})+N({\mathcal{P}}_{\widehat{G/v}})+2\leq
6^{\frac{n-2}{2}}+6^{\frac{n-2}{2}}+2=12\cdot 6^{\frac{n}{2}-2}+2\leq 14\cdot
6^{\frac{n}{2}-2}<6^{\frac{n-1}{2}}.$

In addition, $N({\mathcal{P}}_{\widehat{G}})=14\cdot 6^{\frac{n}{2}-2}$ if and
only if $n=4$ and both $G-v$ and $G/v$ are $K_{2}$ if and only if $G$ is a
triangle.

Case 2.2 ($N_{G}[v]\neq[n-1]$). From Proposition 3.6 (1), we have

$N({\mathcal{P}}_{\widehat{G}})\geq
N({\mathcal{P}}_{\widehat{G-v}})+N({\mathcal{P}}_{\widehat{G/v}})>2^{n-2}+2^{n-2}=2^{n-1},$

and

(10) $\displaystyle N({\mathcal{P}}_{\widehat{G}})$ $\displaystyle\leq$
$\displaystyle
N({\mathcal{P}}_{\widehat{G-v}})+2N({\mathcal{P}}_{\widehat{G-N_{G}[v]}})+N({\mathcal{P}}_{\widehat{G/v}})$
(11) $\displaystyle\leq$ $\displaystyle 6^{\frac{n-2}{2}}+2\cdot
6^{\frac{n-4}{2}}+6^{\frac{n-2}{2}}$ (12) $\displaystyle=$
$\displaystyle\frac{7}{3}\cdot 6^{\frac{n-2}{2}}=14\cdot
6^{\frac{n}{2}-2}<6^{\frac{n-1}{2}}.$

Suppose that $n$ is even. We will show that
$N({\mathcal{P}}_{\widehat{G}})=14\cdot 6^{\frac{n}{2}-2}$ if and only if $G$
is a disjoint union of several edges with the triangle.

(If) If $G$ is a disjoint union of several edges with the triangle, then
$\widehat{G}$ is a disjoint union of several triangles with $K_{4}$. Since
$N({\mathcal{P}}_{K_{3}})=6$ and $N({\mathcal{P}}_{K_{4}})=14$,
$N({\mathcal{P}}_{\widehat{G}})=14\cdot 6^{\frac{n}{2}-2}$.

(Only if) Suppose that $N({\mathcal{P}}_{\widehat{G}})=14\cdot
6^{\frac{n}{2}-2}$. From (10) – (12) above, by the hypothesis of induction,
each of $G-v$, $G/v$ and $G-N_{G}[v]$ is a disjoint union of several edges,
and the number of vertices of $G-N_{G}[v]$ is $n-4$. Then $\deg(v)=2$. Let
$N_{G}(v)=\\{v_{1},v_{2}\\}$. Since $G/v$ is a disjoint union of several edges
and since $\\{v_{1},v_{2}\\}$ is an edge of $G/v$,
$N_{G/v}(v_{1})=\\{v_{2}\\}$ and $N_{G/v}(v_{2})=\\{v_{1}\\}$. Since $G-v$ is
a disjoint union of several edges, $\\{v_{1},v_{2}\\}$ is an edge of $G$. In
addition, since $G-N_{G}[v]$ is a disjoint union of several edges, $G$ is a
disjoint union of several edges with the triangle $(v,v_{1},v_{2})$. ∎

######  Remark 3.8.

Given a graph $G$ on the vertex set $[n]$, let $Q_{ij}(G)$ denote the number
of subset $S\subset[n]$ with $i=|S|$ and $j=c(G[S])$. Then the polynomial

$Q(G;x,y)=\sum_{i=0}^{n}\sum_{j=0}^{n}Q_{ij}(G)x^{i}y^{j}$

is called the subgraph component polynomial of $G$. From Lemma 3.4, it follows
that $Q(G;1,2)$ gives an upper bound of $N({\mathcal{P}}_{\widehat{G}})$.
Although it seems to be difficult to apply the theory of subgraph component
polynomials to our problem directly, the idea of the proof of Proposition 3.6
is inspired by [17, Theorem 13].

##  4\. Join graphs

In the present section, we extend Theorem 1.3 to join graphs by giving a proof
of Theorem 1.4.

######  Lemma 4.1.

Let $G_{1}=(V,E)$ and $G_{2}=(V^{\prime},E^{\prime})$ be graphs with $V\cap
V^{\prime}=\emptyset$, $|V|=n_{1}$, and $|V^{\prime}|=n_{2}$. For each
$i=1,2$, let $m_{i}$ be the number of connected components of $G_{i}$. Then we
have

$N({\mathcal{P}}_{G_{1}+G_{2}})\ \ \leq\ \
N({\mathcal{P}}_{\widehat{G_{1}}})+N({\mathcal{P}}_{\widehat{G_{2}}})+2^{m_{1}}+2^{m_{2}}-2+4(2^{n_{1}-1}-1)(2^{n_{2}-1}-1).$

###### Proof.

We define a partition ${\rm FS}(G_{1}+G_{2})={\rm FS}_{1}\sqcup{\rm
FS}_{2}\sqcup{\rm FS}_{3}\sqcup{\rm FS}_{4}$, where

$\displaystyle{\rm FS}_{1}$ $\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}(G_{1}+G_{2}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }\\\ V\cap V_{1}\neq\emptyset,V\cap
V_{2}\neq\emptyset\mbox{ and }V^{\prime}\subset V_{1}\end{array}\right\\},$
$\displaystyle{\rm FS}_{2}$ $\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}(G_{1}+G_{2}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }\\\ V^{\prime}\cap
V_{1}\neq\emptyset,V^{\prime}\cap V_{2}\neq\emptyset\mbox{ and }V\subset
V_{1}\end{array}\right\\},$ $\displaystyle{\rm FS}_{3}$ $\displaystyle:=$
$\displaystyle\left\\{H\in{\rm FS}(G_{1}+G_{2}):\mbox{the bipartition of
}H\mbox{ is }V\sqcup V^{\prime}\right\\},$ $\displaystyle{\rm FS}_{4}$
$\displaystyle:=$ $\displaystyle\left\\{H\in{\rm
FS}(G_{1}+G_{2}):\begin{array}[]{c}\mbox{the bipartition of }H\mbox{ is
}V_{1}\sqcup V_{2},\mbox{ where }\\\ V\cap V_{1}\neq\emptyset,V\cap
V_{2}\neq\emptyset,V^{\prime}\cap V_{1}\neq\emptyset,V^{\prime}\cap
V_{2}\neq\emptyset\end{array}\right\\}.$

Claim 1. There is an injection $\varphi:{\rm FS}_{1}\rightarrow{\rm
FS}(\widehat{G_{1}})$ such that $\mu(H)=\mu(\varphi(H))$.

Let $H\in{\rm FS}_{1}$. Then $V\cap V_{2}$ is a dominating set of $G_{1}$.
Hence the graph $H^{\prime}$ obtained from $H$ by contracting the vertices in
$V^{\prime}$ to one vertex is a facet subgraph of $\widehat{G_{1}}$. Since
$(G_{1}+G_{2})[V_{1}]$ is connected, we have
$\mu(H)=\mu(H^{\prime})=2^{c(G_{1}[V_{2}])}$.

Claim 2. There is an injection $\varphi:{\rm FS}_{2}\rightarrow{\rm
FS}(\widehat{G_{2}})$ such that $\mu(H)=\mu(\varphi(H))$.

It follows from the same argument as in Claim 1.

Claim 3. ${\rm FS}_{3}=\\{H_{0}\\}$ where $\mu(H_{0})=2^{m_{1}}+2^{m_{2}}-2$.

Let $H^{\prime}$ denote the graph obtained from $H$ by contracting each
connected component of $G_{1}[V]$ and that of $G_{2}[V^{\prime}]$ to one
vertex. From Proposition 2.1, $\mu(H_{0})=N({\mathcal{P}}_{H^{\prime}})$.
Since $H^{\prime}$ is a complete bipartite graph with partition
$V_{1}^{\prime}\sqcup V_{2}^{\prime}$, where $|V_{1}^{\prime}|=m_{1}$ and
$|V_{2}^{\prime}|=m_{2}$, it follows that $\mu(H_{0})=2^{m_{1}}+2^{m_{2}}-2$.

Claim 4. $|{\rm FS}_{4}|\leq 2(2^{n_{1}-1}-1)(2^{n_{2}-1}-1)$ and $\mu(H)=2$
for each $H\in{\rm FS}_{4}$.

The number of facet subgraphs $H\in{\rm FS}_{4}$ is at most
$2(2^{n_{1}-1}-1)(2^{n_{2}-1}-1)$ by considering the possibility of $V_{1}$
and $V_{2}$. If $H\in{\rm FS}_{4}$, then both $(G_{1}+G_{2})[V_{1}]$ and
$(G_{1}+G_{2})[V_{2}]$ are connected, and hence $\mu(H)=2$ from Proposition
2.1.

From Claims 1, 2, 3, and 4 we have

$N({\mathcal{P}}_{G_{1}+G_{2}})\ \ \leq\ \
N({\mathcal{P}}_{\widehat{G_{1}}})+N({\mathcal{P}}_{\widehat{G_{2}}})+2^{m_{1}}+2^{m_{2}}-2+4(2^{n_{1}-1}-1)(2^{n_{2}-1}-1),$

as desired. ∎

We now prove the main theorem of the present paper.

###### Proof of Theorem 1.4.

From Proposition 2.11, we may assume that $n\geq 5$. Let $n_{1}=|V|$ and
$n_{2}=|V^{\prime}|$. From Theorem 1.3, we may assume that $G_{1}+G_{2}$ has
no vertices of degree $n-1$. In addition, if both $G_{1}$ and $G_{2}$ are
empty, then $G_{1}+G_{2}$ is a complete bipartite graph and hence satisfies
the assertion. Thus we may assume that

  * (i)

each $G_{i}$ has no vertices of degree $n_{i}-1$,

  * (ii)

$n_{1}\geq n_{2}\geq 2$, and $n\geq 5$,

  * (iii)

either $G_{1}$ or $G_{2}$ has at least one edge.

First, we will show $N({\mathcal{P}}_{G_{1}+G_{2}})>3\cdot
2^{\frac{n-1}{2}}-2\ (>2^{\frac{n}{2}+1}-2)$. Let ${\rm FS}_{3}=\\{H_{0}\\}$
and ${\rm FS}_{4}$ denote the sets defined in the proof of Lemma 4.1. Let
$\\{i,j\\}$ be an edge of $G_{1}$. Then a maximal spanning bipartite subgraph
of $G_{1}+G_{2}$ with partition $V_{1}\sqcup V_{2}$ where $i\in V_{1}$, $j\in
V_{2}$, $V_{1}\cap V^{\prime}\neq\emptyset$ and $V_{2}\cap
V^{\prime}\neq\emptyset$ belongs to ${\rm FS}_{4}$. The number of such
partitions equals to $2^{n_{1}-2}(2^{n_{2}}-2)=2^{n-2}-2^{n_{1}-1}$. Hence
$|{\rm FS}_{4}|\geq 2^{n-2}-2^{n_{1}-1}$. Similarly, if $G_{2}$ has an edge,
then $|{\rm FS}_{4}|\geq 2^{n-2}-2^{n_{2}-1}$. Since $n-2\geq n_{1}\geq
n_{2}$, we have $|{\rm FS}_{4}|\geq 2^{n-2}-2^{n-3}=2^{n-3}$. Then

$N({\mathcal{P}}_{G_{1}+G_{2}})\geq 2\cdot|{\rm FS}_{4}|+\mu(H_{0})\geq
2^{n-2}+2^{m_{1}}+2^{m_{2}}-2\ (>2^{n-2}).$

If $n=5$, then $(n_{1},n_{2})=(3,2)$ and $G_{2}$ is an empty graph with 2
vertices. Since $m_{2}=2$ and $m_{1}\geq 1$,

$(2^{n-2}+2^{m_{1}}+2^{m_{2}}-2)-(3\cdot 2^{\frac{n-1}{2}}-2)\geq 2>0.$

If $n=6$, then $2^{n-2}-(3\cdot 2^{\frac{n-1}{2}}-2)=6(3-2\sqrt{2})>0.$ If
$n\geq 7$, then

$2^{n-2}-(3\cdot
2^{\frac{n-1}{2}}-2)=2^{\frac{n-1}{2}}\left(2^{\frac{n-3}{2}}-3\right)+2>0.$

Thus we have $N({\mathcal{P}}_{G_{1}+G_{2}})>3\cdot 2^{\frac{n-1}{2}}-2$.

Finally, we will show $N({\mathcal{P}}_{G_{1}+G_{2}})<14\cdot
6^{\frac{n}{2}-2}\ (<6^{\frac{n-1}{2}})$.

Case 1 ($n_{2}=2$). From (i) above, $G_{2}$ is an empty graph with 2 vertices
and hence $N({\mathcal{P}}_{\widehat{G_{2}}})=4$. From (iii), $G_{1}$ has at
least one edge. In particular, the number of connected components of $G_{1}$
is $m_{1}<n_{1}=n-2$. From Lemma 4.1,

$\displaystyle N({\mathcal{P}}_{G_{1}+G_{2}})$ $\displaystyle\leq
N({\mathcal{P}}_{\widehat{G_{1}}})+N({\mathcal{P}}_{\widehat{G_{2}}})+2^{m_{1}}+2^{m_{2}}-2+4(2^{n_{1}-1}-1)(2^{n_{2}-1}-1)$
$\displaystyle\leq
N({\mathcal{P}}_{\widehat{G_{1}}})+4+2^{n-3}+2^{2}-2+4(2^{n-3}-1)(2^{2-1}-1)$
$\displaystyle=N({\mathcal{P}}_{\widehat{G_{1}}})+5\cdot 2^{n-3}+2.$

If $n=5$, then $(n_{1},n_{2})=(3,2)$ and $G_{2}$ is an empty graph with 2
vertices. From (i) and (iii) above, $G_{1}$ has exactly one edge. Thus
$N({\mathcal{P}}_{\widehat{G_{1}}})=12$, and hence
$N({\mathcal{P}}_{\widehat{G_{1}}})+5\cdot 2^{n-3}+2=34<14\sqrt{6}$. Suppose
that $n\geq 6$. From Theorem 1.3,

$14\cdot 6^{\frac{n}{2}-2}-(6^{\frac{n}{2}-1}+5\cdot 2^{n-3}+2)=48\cdot
6^{\frac{n}{2}-3}-40\cdot 4^{\frac{n}{2}-3}-2>0.$

Thus we have $N({\mathcal{P}}_{G_{1}+G_{2}})<14\cdot 6^{\frac{n}{2}-2}$.

Case 2 ($n_{2}\geq 3$). Then $n\geq 6$. From Theorem 1.3 and Lemma 4.1,

$\displaystyle N({\mathcal{P}}_{G_{1}+G_{2}})$ $\displaystyle\leq
N({\mathcal{P}}_{\widehat{G_{1}}})+N({\mathcal{P}}_{\widehat{G_{2}}})+2^{m_{1}}+2^{m_{2}}-2+4(2^{n_{1}-1}-1)(2^{n_{2}-1}-1)$
$\displaystyle\leq
6^{\frac{n_{1}}{2}}+6^{\frac{n_{2}}{2}}+2^{n_{1}}+2^{n_{2}}-2+4(2^{n_{1}-1}-1)(2^{n_{2}-1}-1)$
$\displaystyle=6^{\frac{n_{1}}{2}}+6^{\frac{n_{2}}{2}}+2^{n_{1}+n_{2}}-2^{n_{1}}-2^{n_{2}}+2$
$\displaystyle\leq 2\cdot 6^{\frac{n-3}{2}}+2^{n}-14.$

If $n=6$, then $14\cdot 6^{\frac{n}{2}-2}-(2\cdot
6^{\frac{n-3}{2}}+2^{n}-14)=34-12\sqrt{6}>0$. If $n\geq 7$, then we have

$14\cdot 6^{\frac{n}{2}-2}-(2\cdot
6^{\frac{n-3}{2}}+2^{n}-14)=(84\sqrt{6}-72)\cdot 6^{\frac{n-7}{2}}-128\cdot
4^{\frac{n-7}{2}}+14>0.$

(Here, $84\sqrt{6}-72\risingdotseq 133.76$.) Thus we have
$N({\mathcal{P}}_{G_{1}+G_{2}})<14\cdot 6^{\frac{n}{2}-2}$. ∎

## Acknowledgement

The second author is supported by Grant-in-Aid for JSPS Fellows 23KJ2117.

## References

  * [1] V. Batyrev, Dual polyhedra and mirror symmetry for Calabi-Yau hypersurfaces in toric varieties, J. Algebraic Geom., 3 (1994), 493–535.
  * [2] B. Braun and K. Bruegge, Facets of symmetric edge polytopes for graphs with few edges, J. Integer Seq. 26 (2023), Article 23.7.2.
  * [3] B. Braun and K. Bruegge and M. Kahle, Facets of random symmetric edge polytopes, degree sequences, and clustering, Discrete Math. Theor. Comput. Sci. 25:2 (2023), #16.
  * [4] T. Chen, R. Davis, and E. Korchevskaia, Facets and facet subgraphs of symmetric edge polytopes, Discrete Appl. Math. 328 (2023), 139–153.
  * [5] T. Chen, R. Davis and D. Mehta, Counting equilibria of the Kuramoto model using birationally invariant intersection index, SIAM J. Appl. Algebra Geom., 2 (2018), 489–507.
  * [6] A. D’Alì, E. Delucchi and M. Michałek, Many faces of symmetric edge polytopes, Electron. J. Combin. 29 (2022), Paper No. 3.24.
  * [7] A. D’Alì, M. Juhnke-Kubitzke and M. Koch, On a generalization of symmetric edge polytopes to regular matroids, arXiv:2307.04933
  * [8] A. D’Alì, M. Juhnke-Kubitzke, D. Köhne, and L. Venturello, On the gamma-vector of symmetric edge polytopes, SIAM J. Discrete Math. 37.2 (2023): 487-515.
  * [9] A. Higashitani, Smooth Fano polytopes arising from finite directed graphs, Kyoto J. Math. 55 (2015) 579–592.
  * [10] A. Higashitani, K. Jochemko, and M. Michałek, Arithmetic aspects of symmetric edge polytopes, Mathematika 65 (2019), 763–784.
  * [11] T. Kálmán and L. Tóthmérész, Ehrhart theory of symmetric edge polytopes via ribbon structures, preprint. arXiv:2201.10501.
  * [12] T. Matsui, A. Higashitani, Y. Nagazawa, H. Ohsugi, and T. Hibi, Roots of Ehrhart polynomials arising from graphs, J. Algebraic Combin. 34 (2011), 721–749.
  * [13] B. Nill, Gorenstein toric Fano varieties, Manuscripta Math. 116 (2005) 183–210.
  * [14] B. Nill, Classification of pseudo-symmetric simplicial reflexive polytopes, in “Algebraic and Geometric Combinatorics” (C. A. Athanasiadis et al., eds.), Contemp. Math. 423, AMS, 2006, pp. 269–282.
  * [15] H. Ohsugi and A. Tsuchiya, Symmetric edge polytopes and matching generating polynomials, Combinatorial Theory 1 (2021) # 9.
  * [16] H. Ohsugi and A. Tsuchiya, The $h^{*}$-polynomials of locally anti-blocking lattice polytopes and their $\gamma$-positivity, Discrete Comput. Geom. 66 (2021), 701–722.
  * [17] P. Tittmann, I. Averbouch and J.A. Makowsky, The enumeration of vertex induced subgraphs with respect to the number of components, European J. Combin. 32 (2011), 954–974.