<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{diagbox}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\newcommand{\conv}[1]{\mathrm{conv}\{#1\}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\maxf}{\mathrm{maxf}}
\newcommand{\minf}{\mathrm{minf}}
\newcommand{\maxfac}{\mathrm{Maxf}}
\newcommand{\minfac}{\mathrm{Minf}}
\newcommand{\PG}{P_G}
\newcommand{\PH}{P_H}
\newcommand{\facets}{N}
\newcommand{\CB}{\mathrm{CB}}
\newcommand{\windmill}{\mathrm{WM}}
\newcommand{\Ds}{\displaystyle}

\usepackage{rotating}
\tikzstyle{vertex}=[circle, draw, inner sep=0pt, minimum size=4pt]
\newcommand{\vertex}{\node[vertex]}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf  Facets of Symmetric Edge Polytopes for \\
\vskip .1in
Graphs with Few Edges}
\vskip 1cm
Benjamin Braun and Kaitlin Bruegge\\
Department of Mathematics\\
University of Kentucky\\
Lexington, KY 40506-0027\\
USA \\
\href{mailto:benjamin.braun@uky.edu}{\tt benjamin.braun@uky.edu}\\
\href{mailto:kaitlin_bruegge@uky.edu}{\tt kaitlin\_bruegge@uky.edu}
\end{center}


\begin{abstract}
Symmetric edge polytopes, also called adjacency polytopes, are lattice
polytopes determined by simple undirected graphs.  We introduce the
integer array giving the maximum number of facets of a symmetric edge
polytope for a connected graph having a fixed number of vertices and edges
and the corresponding array of minimal values.  We establish formulas for
the number of facets obtained in several classes of sparse graphs, and
provide partial progress toward conjectures that identify facet-maximizing
graphs in these classes.  These formulas are combinatorial in nature, and
lead to independently interesting observations and conjectures regarding
integer sequences defined by sums of products of binomial coefficients.
\end{abstract}


\section{Introduction}\label{secintro}

Given a finite graph \(G\), there are many ways to construct a lattice polytope using \(G\) as input: graphical zonotopes, edge polytopes, matching polytopes, stable set polytopes, Laplacian simplices, flow polytopes, and others.
Of recent interest is the \emph{symmetric edge polytope} \(P_G\), introduced by Matsui, Higashitani, Nagazawa, Ohsugi, and Hibi~\cite{matsuietal2011}.
These are known as \emph{adjacency polytopes} in some applied settings~\cite{chen2017counting}.
Symmetric edge polytopes are of interest in several areas, including the study of Ehrhart theory and applications to algebraic Kuramoto equations.
These polytopes have been the subject of intense recent study~\cite{chen2021facets,chen2017counting,chen2020graphadjacency,dali2022gammavector,dalidelucchimichalek,higashitanijochemkomateusz,kalman2022ehrhart,matsuietal2011,smoothfanoehrhart2012,symmetricedgematchingpolys}.

In this paper, we study the number of facets of \(P_G\) for connected graphs, with an emphasis on those graphs having few edges.
Our study is motivated by the following question: for a fixed number of vertices and edges, what properties of connected graphs lead to symmetric edge polytopes with either a large or small number of facets?
This leads us to the following definition.

\begin{definition}\label{defMF}
For \(n\geq 2\) and \(m\geq n-1\), define \(\maxf(n,m)\) to be the maximum number of facets of a symmetric edge polytope for a connected graph having \(n\) vertices and \(m\) edges, and similarly define \(\minf(n,m)\) to be the minimum number of facets.
For \(n\geq 2\), we define \(\maxfac(n)\) to be the maximum number of facets of a symmetric edge polytope for a connected graph having \(n\) vertices, and similarly define \(\minfac(n)\) to be the minimum number.
\end{definition}

The first few values of \(\maxf(n,m)\)~\seqnum{A360408} are given in Table~\ref{tabmaxf}.
The first few values of \(\minf(n,m)\)~\seqnum{A360409} are given in Table~\ref{tabminf}.
The sequence $\maxfac(n)$ is given by 
\[
2, 6, 14, 36, 84, 216, 504, 1296,\ldots \, 
\]
while the sequence $\minfac(n)$ is given by
\[
2, 4, 6, 10, 14, 22, 30, 46,\ldots
\]

Note that the conjectured sequence~\seqnum{A027383} for $\minfac(n)$ has been previously studied.
The problem of determining $\maxf(n,m)$ and $\minf(n,m)$ is challenging, in part due to the complicated combinatorial structures that describe the facets of \(P_G\).
Our experimental data suggest that facet-maximizing graphs can be obtained as wedges of odd cycles; how broadly this holds for general $n$ and $m$ beyond relatively sparse graphs is not clear.
Based on computational evidence obtained with SageMath~\cite{sage}, we offer the following conjecture regarding terms of the sequences $\maxfac(n)$ and $\minfac(n)$ in general (all undefined terms below are defined in subsequent sections).

\begin{table}[t]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{c|ccccccccccccccc}
\hline
\diagbox{$n$} {$m-n+1$} &amp; 0  &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 \\
\hline 
2 &amp; 2  \\
3 &amp;  4 &amp; 6 \\
4 &amp;  8 &amp; 12 &amp; 12 &amp; 14 \\
5 &amp;  16 &amp; 30 &amp; 36 &amp; 28 &amp; 28 &amp; 28 &amp; 30 \\
6 &amp;  32 &amp; 60 &amp; 72 &amp; 72 &amp; 84 &amp; 68 &amp; 68 &amp; 60 &amp; 60 &amp; 60 &amp; 62 \\
7 &amp;  64 &amp; 140 &amp; 180 &amp; 216 &amp; 168 &amp; 168 &amp; 196 &amp; 180 &amp; 148 &amp; 148 &amp; 132 &amp; 132 &amp; 124 
\end{tabular}%
}
\caption{$\maxf(n,m)$.}
\label{tabmaxf}
\end{table}

\begin{table}[t]
\centering
\resizebox{\columnwidth}{!}{%
\begin{tabular}{c|cccccccccccccc}
\hline
\diagbox{$n$} {$m-n+1$} &amp; 0  &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 &amp; 11 &amp; 12 &amp; 13 \\
\hline 
2 &amp; 2  \\
3 &amp;  4 &amp; 6 \\
4 &amp;  8 &amp; 6 &amp; 12 &amp; 14 \\
5 &amp;  16 &amp; 12 &amp; 10 &amp; 22 &amp; 26 &amp; 28 &amp; 30 \\
6 &amp;  32 &amp; 20 &amp; 18 &amp; 16 &amp; 14 &amp; 42 &amp; 54 &amp; 56 &amp; 58 &amp; 60 &amp; 62 \\
7 &amp;  64 &amp; 40 &amp; 32 &amp; 28 &amp; 26 &amp; 24 &amp; 22 &amp; 78 &amp; 102 &amp; 106 &amp; 116 &amp; 118 &amp; 120 &amp; 122 
\end{tabular}%
}
\caption{$\minf(n,m)$.}
\label{tabminf}
\end{table}

\begin{conjecture}\label{conjmaxmin}
    Let $n\geq 3$.
    \begin{enumerate}
        \item For $n=2k+1$, we have $\maxfac(n)=6^k$, which is attained by a wedge of $k$ cycles of length three.
        \item For $n=2k$, we have $\maxfac(n)=14\cdot 6^{k-2}$, which is attained by a wedge of $K_4$ with $k-2$ cycles of length three.
        \item For $n=2k+1$, we have $\minfac(n)=3\cdot2^k-2$, which is attained by $K_{k,k+1}$.
        \item For $n=2k$, we have $\minfac(n)=2^{k+1}-2$, which is attained by $K_{k,k}$.
    \end{enumerate}
\end{conjecture}

The fact that the conjectured max and min values in Cases~1 and~2 of Conjecture~\ref{conjmaxmin} are attained by a wedge follows from Proposition~\ref{propwedgesmultiply} below, while the analogous values for bipartite graphs in Cases~3 and~4 were established by Higashitani, Jochemko, and Micha\l ek~\cite{higashitanijochemkomateusz}.

It is known that the symmetric edge polytope for every tree on $n$ vertices is combinatorially a cross polytope and thus has $2^{n-1}$ facets, hence $\maxf(n,n-1)=2^{n-1}$.
More generally, the number of facets for symmetric edge polytopes can be derived using combinatorial tools.
Specifically, a combinatorial description of the facet-defining hyperplanes of \(P_G\) was given by  Higashitani, Jochemko, and Micha\l ek~\cite{higashitanijochemkomateusz}.
Further, Chen, Davis, and Korchevskaia~\cite{chen2021facets} give a combinatorial description of the faces of \(P_G\) that utilizes special subgraphs of \(G\).

It follows from Definition~\ref{defpg} below that symmetric edge polytopes are centrally symmetric lattice polytopes.
Symmetric edges polytopes have also been shown to be reflexive and terminal~\cite{higashitanifanopolytopes}.
Further, Higashitani~\cite[Theorem 3.3]{higashitanifanopolytopes} proved that centrally symmetric simplicial reflexive polytopes are precisely the symmetric edge polytopes of graphs without even cycles.
In Case~1 of Conjecture~\ref{conjmaxmin}, the symmetric edge polytopes arising from wedges of cycles of length three fall within this family.
This is related to a result due to Nill~\cite[Corollary 4.4]{NillClassification} stating that the maximum number of facets for every pseudo-symmetric reflexive simplicial \(d\)-polytope \(P\) is \(6^{d/2}\) and that the maximum is attained if and only if \(P\) is a free sum of \(d/2\) copies of \(P_{K_3}\).
Thus, Conjecture~\ref{conjmaxmin} aligns with existing results regarding these polytopes.

In this work, we investigate the sequences $\maxf(n,n)$ and $\maxf(n,n+1)$.
We provide an exact result for $\maxf(n,n)$ and provide partial progress toward a conjectured value of $\maxf(n,n+1)$.
The use of combinatorial tools for this analysis  produces independently interesting integer sequences defined by sums of products of binomial coefficients.

This paper is structured as follows.
In Section~\ref{secbackground}, we provide necessary definitions and background.  
In Section~\ref{secdisjointcycle}, we give formulas for the number of facets and discuss facet-maximizers among some sparse connected graphs, namely graphs on \(n\) vertices with \(n\) or \(n+1\) edges where every pair of cycles present is edge-disjoint.
In these cases, Theorems~\ref{thmnnmax}~and~\ref{thmdisjointcycleslessthanMn} respectively describe facet-maximizing graphs. 
In Section~\ref{secoverlapcycle}, we discuss facet counts for graphs constructed from internally disjoint paths connected at their endpoints and give formulas in Propositions~\ref{propsameparity}~and~\ref{propfacetsofgencbmixed}.
As a special case of this, we get results about the number of facets arising from graphs with \(n\) vertices and \(n+1\) edges where the cycles share at least one edge, and we make progress toward generalizing Theorem~\ref{thmdisjointcycleslessthanMn} to this class of graphs. 
In Section~\ref{secconjectures}, we give several conjectures regarding facet-maximizing graphs in certain families.  
We also discuss computational evidence supporting these conjectures.

\section{Background}\label{secbackground}

\begin{definition}\label{defpg}
Let \(G\) be a graph on the vertex set \([n]=\{1,\ldots,n\}\) and edge set \(E=E(G)\).
Let \(e_i\) denote the \(i\)-th standard basis vector in \(\R^n\) and let \(\conv{X}\) denote the convex hull of a subset \(X\subset \R^n\).
The \emph{symmetric edge polytope} for $G$ is
\[
\PG:=\conv{\pm(e_i-e_j): \{i,j\}\in E(G)}\,.
\]

We denote by \(N(P)\) the number of facets of a polytope \(P\).
We denote by both \(N(\PG)\) and \(N(G)\) the number of facets of \(\PG\).
\end{definition}

\begin{example}
Let \(G\) be the path with vertices \(\{1,2,3\}\) and edges \(\{12,23\}\).
Then 
\[
\PG=\conv{\pm(e_1-e_2),\pm(e_2-e_3)}\subset \R^3
\]
is a \(4\)-gon contained in the orthogonal complement of the vector \(\langle 1,1,1\rangle\). 
This polygon has four 1-dimensional faces.
Thus, we have \(\facets(\PG)=4\).
\end{example}

In general, the machinery used to count the facets of $\PG$ are functions \(f:V\rightarrow \Z\) on the set \(V\) of vertices in \(G\) satisfying certain properties. 
It is known~\cite[Theorem 3.1]{higashitanijochemkomateusz} that the facets of \(\PG\) are in bijection with these functions. 

\begin{theorem}[Higashitani, Jochemko, Micha\l ek \cite{higashitanijochemkomateusz}]\label{thmfacetdescription}
Let \(G=(V,E)\) be a finite simple connected graph.
Then \(f:V\rightarrow\Z\) is facet-defining if and only if both of the following hold.
\begin{enumerate}
    \item[(i)]For every edge \(e=uv\) we have \(|f(u)-f(v)|\leq 1\).
    \item[(ii)] The subset of edges \(E_f=\{e=uv\in E\::\: |f(u)-f(v)|= 1\}\) forms a spanning connected subgraph of \(G\).
\end{enumerate}
\end{theorem}

As symmetric edge polytopes are contained in the hyperplane orthogonal to the span of the vector where every entry is one, two facet-defining functions are identified if they differ by a common constant.
The spanning connected subgraphs with edge sets \(E_f\) arising in Theorem~\ref{thmfacetdescription}, called \emph{facet subgraphs}, have further structure. 

\begin{lemma}[Chen, Davis, Korchevskaia \cite{chen2021facets}]\label{lemfacetsubgraphs}
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\).
\end{lemma}

Lemma~\ref{lemfacetsubgraphs} provides a strategy for identifying the facets of \(P_G\) combinatorially: first identify the maximal connected spanning bipartite subgraphs of \(G\), then determine the valid integer labelings of the vertices.
Facet counts for symmetric edge polytopes are known for certain classes of graphs. 
A class of particular interest to us is cycles.
Let \(C_n\) denote the cycle with \(n\) edges and let \(Q_n\) denote the path with \(n\) edges.

\begin{lemma}\label{lemcyclefacets}
For every \(m\),
\[
\facets(P_{C_m}) = \begin{cases}
\binom{m}{m/2}, &amp; \text{if $m$ is even;}\\
m\binom{m-1}{(m-1)/2}, &amp; \text{if $m$ is odd.}
\end{cases}
\]
\end{lemma}
\begin{proof}
For even \(m\), the facets of \(P_{C_m}\) are identified and counted in~\cite[Proposition~12]{chen2017counting}, and for odd \(m\) in~\cite[Remark~4.3]{NillClassification}.
\end{proof}

Though the two-cycle is a multigraph (and thus its symmetric edge polytope is not defined), its facet-defining functions would be exactly the facet-defining functions of a graph on two vertices with a single edge.  
This is consistent with the formula in Lemma~\ref{lemcyclefacets}.

For a graph \(G\) that is constructed by identifying two graphs at a single vertex, there is a relationship between the facets of \(\PG\) and the facets of the subgraphs.  

\begin{definition}
For graphs \(G\) and \(H\), let \(G\vee H\) denote a graph obtained by identifying a vertex in \(G\) with a vertex in \(H\).
We call $G\vee H$ a \emph{wedge} or \emph{join}.
\end{definition}

Note that we do not specify a choice of identification points when defining \(G\vee H\), as by the following proposition every such choice yields a symmetric edge polytope with the same number of facets.

\begin{proposition}\label{propwedgesmultiply}
For connected graphs \(G\) and \(H\),
\[
\facets(P_{G\vee H})=\facets(\PG)\cdot\facets(P_H).
\]
\end{proposition}

\begin{proof}
This follows from the fact that \(P_{G\vee H}\) is the free sum \(\PG \oplus \PH\)~\cite[Proposition~4.2]{osughitsuchiya2020} (also called the direct sum) and the number of facets is multiplicative for free sums~\cite{HenkRichterZiegler}.
\end{proof}


\section{Graphs with few edges and disjoint cycles}\label{secdisjointcycle}


We consider the symmetric edge polytopes for classes of connected graphs where the number of edges is small relative to the number of vertices.
For every tree \(T\) on \(n\) vertices, we obtain \(\facets(T)=2^{n-1}\) using Proposition~\ref{propwedgesmultiply} since \(T\) can be constructed as a wedge of \(n-1\) single edges with an appropriate choice of identification points. 
Thus, it follows that $\maxf(n,n-1)=2^{n-1}$.

Considering next the sequence $\maxf(n,n)$, every connected graph with an equal number of vertices and edges has a unique cycle and hence can be constructed as a wedge of that cycle with trees. 
Therefore, we can count the facets of \(\PG\) for every such graph \(G\) and determine the maximum possible facet number arising from a graph with \(n\) vertices and \(n\) edges.

\begin{definition}\label{defcnm}
Let \(C(n,m)\) denote a graph on \(n\) vertices obtained by joining an \(m\)-cycle with a path graph on \(n-m\) edges. 
\end{definition}

\begin{figure}
\begin{center}
\begin{tikzpicture}
    \vertex[fill](1) at (-1,2.9) {};
	\vertex[fill] (2) at (0,2) {};
	\vertex[fill] (3) at (1,2.5) {};
	\vertex[fill](4) at (-2,2) {};
	\vertex[fill](5) at (-1.5,0.8) {};
	\vertex[fill] (6) at (-0.5,0.8) {};
	\vertex[fill] (7) at (1,1.5) {};
	\draw[thick] (1)--(2) {};
	\draw[thick] (1)--(4) {};
	\draw[thick] (4)--(5) {};
	\draw[thick] (2)--(6) {};
	\draw[thick] (5)--(6) {};
	\draw[thick] (2)--(3) {};
	\draw[thick] (3)--(7) {};
      \end{tikzpicture}
\end{center}
    \caption{\(C(7,5)\).}
    \label{figcnm}
\end{figure}

\begin{theorem}\label{thmnnmax}
For every connected graph \(H\) with \(n\) vertices and \(n\) edges, the number of facets of \(P_H\) is less than or equal to the number of facets of \(\PG\) for \(G=C(n,n)\) when \(n\) is odd and \(G=C(n,n-1)\) when \(n\) is even. 
Thus, for odd $n$ we have
\[
\maxf(n,n)=n\binom{n-1}{(n-1)/2}
\]
and for even $n$ we have
\[
\maxf(n,n)= 2(n-1)\binom{n-2}{(n-2)/2}\, .
\]
\end{theorem}

\begin{proof}
A connected graph on \(n\) vertices and \(n\) edges has a unique cycle of length \(m\) for some \(3\leq m\leq n\).
Thus, the graph \(G\) is the join of an \(m\)-cycle and \(n-m\) edges. 
By Proposition~\ref{propwedgesmultiply}, we have $\facets(G)=\facets(C(n,m))$.
For \(k\geq 2\), we claim 
\begin{equation}\label{eqncniineq}
\facets(C(n,2k))&lt;\facets(C(n,2k-1))&lt;\facets(C(n,2k+1))\, .
\end{equation}
In other words, if \(m\) is even, then \(\facets(C(n,m-1))\) is greater than \(\facets(C(n,m))\). 
Also, if \(m\) is odd and \(m\leq n-2\), the graph \(C(n,m+2)\) exists, and \(\facets(C(n,m+2))\) is greater than \(\facets(C(n,m))\).  
With these two statements, we see that \(\facets(G)\) is maximized when \(G\) contains the largest odd cycle possible in a graph with \(n\) vertices.

To prove the inequality in~\eqref{eqncniineq}, let 
\[
\mathcal{M}=\frac{2^{n-(2k+1)}(2k-1)!}{(k!)^2}.
\]
Then, by Lemma~\ref{lemcyclefacets} and Proposition~\ref{propwedgesmultiply}, 
\[
\facets(C(n,2k))=\facets(C_{2k})\cdot 2^{n-2k}=\binom{2k}{k}\cdot 2^{n-2k} = 4k\mathcal{M},
\]
\[
\facets(C(n,2k-1))=\facets(C_{2k-1})\cdot 2^{n-(2k-1)}=(2k-1)\binom{2k-2}{k-1}\cdot 2^{n-(2k-1)}=4k^2\mathcal{M},
\]
\[
\facets(C(n,2k+1))=\facets(C_{2k+1})\cdot 2^{n-(2k+1)}=(2k+1)\binom{2k}{k}\cdot 2^{n-(2k+1)}=(4k^2+2k)\mathcal{M},
\]
and the claim holds.
\end{proof}

We next consider the sequence $\maxf(n,n+1)$, which is substantially more challenging than the previous cases.
Every connected, simple graph with \(n\) vertices and \(n+1\) edges can be constructed from a tree on \(n\) vertices by adding two edges.  
Each of these additions induces a cycle in the graph.
For such graphs, we make the following definition and conjecture.

\begin{definition}\label{defMn}
For \(n\geq 3\), let \(M(n)\) be the number of facets of \(\PG\) where 
\[
G:=\begin{cases}
C_{k+1}\vee C_{k-1}, &amp; \text{if $n=2k-1$ and \(k\) even;}\\
C_{k}\vee C_{k},  &amp; \text{if $n=2k-1$ and \(k\) odd;}\\
C_{k+1}\vee C_{k-1}\vee e, &amp; \text{if $n=2k$ and \(k\) even;}\\
C_{k}\vee C_{k}\vee e,  &amp; \text{if $n=2k$ and \(k\) odd.}
\end{cases}
\]
\end{definition}

\begin{figure}
    \begin{center}
\begin{tikzpicture}
    \vertex[fill](1) at (-1,2.9) {};
	\vertex[fill] (2) at (0,2) {};
	\vertex[fill] (3) at (1.5,2.5) {};
	\vertex[fill](4) at (-2,2) {};
	\vertex[fill](5) at (-1.5,0.8) {};
	\vertex[fill] (6) at (-0.5,0.8) {};
	\vertex[fill] (7) at (1.5,1.5) {};
	\draw[thick] (1)--(2) {};
	\draw[thick] (1)--(4) {};
	\draw[thick] (4)--(5) {};
	\draw[thick] (2)--(6) {};
	\draw[thick] (5)--(6) {};
	\draw[thick] (2)--(3) {};
	\draw[thick] (2)--(7) {};
	\draw[thick] (3)--(7) {};
      \end{tikzpicture}
      \end{center}
    \caption{A graph with \(\facets(G)=M(7)\).}
    \label{figM7}
\end{figure}

\begin{conjecture}\label{conjnn1}
For all $n\geq 3$, we have $\maxf(n,n+1)=M(n)$.
\end{conjecture}

Graphs with $n$ vertices and $n+1$ edges fall into two categories: graphs with exactly 2 edge-disjoint cycles, such as those defined in Definition~\ref{deftwocyclewedgegraphs} below, and graphs where the cycles share one or more edges, such as those defined in Definition~\ref{defgenCB} below.
In this section, we show that Conjecture~\ref{conjnn1} is true for the first category.

\begin{theorem}\label{thmdisjointcycleslessthanMn}
For every connected graph \(H\) with \(n\) vertices and \(n+1\) edges where \(H\) contains two edge-disjoint cycles, we have \(\facets(H)\leq M(n)\).
\end{theorem}

Note that Theorem~\ref{thmdisjointcycleslessthanMn} states that, among connected graphs with \(n\) vertices and \(n+1\) edges containing disjoint cycles, a facet-maximizing family arises by creating a graph that as closely as possible resembles the wedge of two equal-length odd cycles. 
The proof relies on the following definition and lemmas.

\begin{definition}\label{deftwocyclewedgegraphs}
Let \(G(n,i,j)\) denote the graph \(C_i\vee C_j\vee Q_{n+1-(i+j)}\).
Note that \(G(n,i,j)\) has \(n\) vertices and \(n+1\) edges.
\end{definition}


\begin{lemma}\label{lemoddcyclebetterthaneven} 
If \(i\) is even, then 
\[
\facets(G(n,i,j)) &lt; \facets(G(n,i-1,j)).
\] 
\end{lemma}

\begin{proof}
Note that \(\facets(G(n,i,j))=\facets(C(n+1-j, i)\vee C_j)\).
Because \(i\) is even, applying~\eqref{eqncniineq} and Proposition~\ref{propwedgesmultiply} yields
\[
\facets(C(n+1-j, i)\vee C_j)&lt;\facets(C(n+1-j, i-1)\vee C_j)=\facets(G(n,i-1,j))\, ,
\]
which completes the proof.
\end{proof}

\begin{lemma}\label{lemevenlydistributedcycles}
For \(i,j,m,\ell\) odd with \(m &lt; i\leq j&lt;l\) and \(i+j=m+\ell\), we have
\[
\facets(C_m\vee C_\ell) &lt; \facets(C_i\vee C_j).
\]
\end{lemma}

\begin{proof}
We show this holds for \(m=i-2\) and \(\ell = j+2\), then the argument follows by induction.
Using Lemma~\ref{lemcyclefacets} and Proposition~\ref{propwedgesmultiply}, we obtain
\[
\facets(C_i\vee C_j)=ij\binom{i-1}{\frac{i-1}{2}}\binom{j-1}{\frac{j-1}{2}}
\]
and
\[
\facets(C_{i-2}\vee C_{j+2})=(i-2)(j+2)\binom{i-3}{\frac{i-3}{2}}\binom{j+1}{\frac{j+1}{2}}.
\]

Letting \(\Ds\mathcal{M}=(i-2)j\binom{i-3}{\frac{i-3}{2}}\binom{j-1}{\frac{j-1}{2}}\), we obtain
\[
\facets(C_{i-2}\vee C_{j+2})=4\mathcal{M}\cdot\frac{j+2}{j+1}&lt;4\mathcal{M}\cdot\frac{i}{i-1}=\facets(C_i\vee C_j).
\]
\end{proof}

We also make use of the following theorem.

\begin{theorem}\label{thmMninequailty}
For all \(n\), we have \(2M(n)\leq M(n+1)\).
\end{theorem}

\begin{proof}
Lemma~\ref{lemcyclefacets} and Proposition~\ref{propwedgesmultiply} imply that
\[
M(n)=\begin{cases}
(k+1)(k-1)\binom{k}{\frac{k}{2}}\binom{k-2}{\frac{k-2}{2}}, &amp;\text{if $n=2k-1$ and $k$ even;}\\
k^2\binom{k-1}{\frac{k-1}{2}}^2,  &amp;\text{if $n=2k-1$ and $k$ odd;}\\
2\cdot M(n-1), &amp; \text{if $n=2k$.}
\end{cases}
\]
When \(n\) is odd, we have \(2\cdot M(n)= M(n+1)\) and we are done.
When \(n\) is even, we consider two cases.

\noindent\emph{Case 1:} If \(n=2k\) with \(k\) even, then \(n+1=2(k+1)-1\) with \(k+1\) odd. Therefore, letting  \(\Ds\mathcal{K}=(k+1)\binom{k}{\frac{k}{2}}\), we have
\[
 M(n)=2\cdot M(2k-1)=2(k+1)(k-1)\binom{k}{\frac{k}{2}}\binom{k-2}{\frac{k-2}{2}}=2(k-1)\binom{k-2}{\frac{k-2}{2}}\cdot\mathcal{K}    
\]
and
\[
M(n+1)=(k+1)^2\binom{k}{\frac{k}{2}}^2=\mathcal{K}^2 \, .
\]

Since 
\[
\begin{split}
\mathcal{K}&amp;=(k+1)\binom{k}{\frac{k}{2}}=\frac{(k+1)k}{\left(\frac{k}{2}\right)^2}\cdot(k-1)\cdot\binom{k-2}{\frac{k-2}{2}}\\&amp;=\frac{4(k+1)}{k}\cdot(k-1)\cdot\binom{k-2}{\frac{k-2}{2}}\geq 4\cdot(k-1)\cdot\binom{k-2}{\frac{k-2}{2}}\, ,    
\end{split}
\]
we see
\[
2\cdot M(n)=4(k-1)\binom{k-2}{\frac{k-2}{2}}\cdot \mathcal{K}\leq \mathcal{K}^2=M(n+1)\, .    
\]

\noindent\emph{Case 2:} If \(n=2k\) with \(k\) odd, then \(n+1=2(k+1)-1\) with \(k+1\) even.
Therefore, letting \(\mathcal{K}=k\binom{k-1}{\frac{k-1}{2}}\), we have
\[
M(n)=2\cdot M(2k-1)=2k^2\binom{k-1}{\frac{k-1}{2}}^2=2\mathcal{K}^2
\]
and
\[
M(n+1)=(k+2)k\binom{k+1}{\frac{k+1}{2}}\binom{k-1}{\frac{k-1}{2}}=(k+2)\binom{k+1}{\frac{k+1}{2}}\cdot\mathcal{K}\, .
\]
Since 
\[
(k+2)\binom{k+1}{\frac{k+1}{2}}=\frac{(k+2)(k+1)}{\left(\frac{k+1}{2}\right)^2}\cdot k\cdot\binom{k-1}{\frac{k-1}{2}}=\frac{4(k+2)}{(k+1)}\cdot \mathcal{K}\geq 4\mathcal{K} \, ,
\]
we see
\[
2\cdot M(n)=4\mathcal{K}^2\leq (k+2)\binom{k+1}{\frac{k+1}{2}}\cdot\mathcal{K}=M(n+1)\, . 
\]
\end{proof}

With these in place, we can prove Theorem~\ref{thmdisjointcycleslessthanMn}.

\begin{proof}[Proof of Theorem~\ref{thmdisjointcycleslessthanMn}]
By Proposition~\ref{propwedgesmultiply}, every such graph \(H\) containing exactly two edge-disjoint cycles of length \(i\) and \(j\) satisfies \(\facets(H)=\facets(G(n,i,j))\).
Thus, it is sufficient to restrict our attention to \(G(n,i,j)\).
By Lemmas~\ref{lemoddcyclebetterthaneven}~and~\ref{lemevenlydistributedcycles}, we can consider only \(G(n,i,j)\) for \(i,j\) odd and as close to \(\frac{i+j}{2}\) as possible. Without loss of generality, suppose \(i\leq j\).

\noindent\emph{Case 1: \(n=2k-1\) and \(k\) even.} Note that, since \(i\) and \(j\) are both odd, we have \(i\leq k-1\) and \(j\leq k+1\).
Also, using  Lemma~\ref{lemcyclefacets} and Proposition~\ref{propwedgesmultiply}, we obtain
\[
\facets(G(n,i,j))=2^{n-(i+j)+1}ij\binom{i-1}{\frac{i-1}{2}}\binom{j-1}{\frac{j-1}{2}}
=2^{2k-(i+j)}\cdot\frac{i!j!}{\left(\frac{i-1}{2}!\right)^2\left(\frac{j-1}{2}!\right)^2} \, .
\]
Similarly,
\[
\begin{split}
    M(n)&amp;=(k+1)(k-1)\binom{k}{\frac{k}{2}}\binom{k-2}{\frac{k-2}{2}}
    \\&amp;=\frac{(k+1)!}{\left(\frac{k}{2}!\right)^2}\cdot \frac{(k-1)!}{\left(\frac{k-2}{2}!\right)^2}
    \\&amp;=\frac{j!}{\left(\frac{j-1}{2}!\right)^2}\cdot\left(\prod_{\substack{\ell =j+1\\\ell\text{ even}}}^{k} \frac{(\ell + 1)\ell}{\left(\frac{\ell}{2}\right)^2} \right)
    \cdot\frac{i!}{\left(\frac{i-1}{2}!\right)^2}\cdot\left(\prod_{\substack{m =i+1\\m\text{ even}}}^{k-2} \frac{(m + 1)m}{\left(\frac{m}{2}\right)^2} \right)
    \\&amp;=2^{2k-(i+j)}\cdot\frac{i!j!}{\left(\frac{i-1}{2}!\right)^2\left(\frac{j-1}{2}!\right)^2}\cdot\left(\prod_{\substack{\ell =j+1\\\ell\text{ even}}}^{k} \frac{\ell + 1}{\ell}\right)\cdot\left(\prod_{\substack{m =i+1\\m\text{ even}}}^{k-2}\frac{m+1}{m}\right)
    \\&amp;\geq\facets(G(n,i,j)).
\end{split}
\]

\noindent\emph{Case 2: \(n=2k-1\) and \(k\) odd.} Note that, by assumption, we have \(i\leq k\) and \(j\leq k\). 
Also, using Lemma~\ref{lemcyclefacets} and Proposition~\ref{propwedgesmultiply}, we obtain
\[
\facets(G(n,i,j))=2^{n-(i+j)+1}ij\binom{i-1}{\frac{i-1}{2}}\binom{j-1}{\frac{j-1}{2}}
=2^{2k-(i+j)}\cdot\frac{i!j!}{\left(\frac{i-1}{2}!\right)^2\left(\frac{j-1}{2}!\right)^2} \, .
\]
Similarly,
\[
\begin{split}
    M(n)&amp;=k^2\binom{k-1}{\frac{k-1}{2}}^2
    \\&amp;=\frac{j!}{\left(\frac{j-1}{2}!\right)^2}\cdot\left(\prod_{\substack{\ell =j+1\\\ell\text{ even}}}^{k-1} \frac{(\ell + 1)\ell}{\left(\frac{\ell}{2}\right)^2} \right)
    \cdot\frac{i!}{\left(\frac{i-1}{2}!\right)^2}\cdot\left(\prod_{\substack{m =i+1\\m\text{ even}}}^{k-1} \frac{(m + 1)m}{\left(\frac{m}{2}\right)^2} \right)
    \\&amp;=2^{2k-(i+j)}\cdot\frac{i!j!}{\left(\frac{i-1}{2}!\right)^2\left(\frac{j-1}{2}!\right)^2}\left(\prod_{\substack{\ell =j+1\\\ell\text{ even}}}^{k-1} \frac{\ell + 1}{\ell}\right)\cdot\left(\prod_{\substack{m =i+1\\m\text{ even}}}^{k-1}\frac{m+1}{m}\right)
    \\&amp;\geq\facets(G(n,i,j)).
\end{split}
\]

\noindent\emph{Case 3: \(n=2k\).} Using Lemma~\ref{lemcyclefacets} and Proposition~\ref{propwedgesmultiply}, we obtain
\[
\facets(G(n,i,j))=2^{n-(i+j)+1}ij\binom{i-1}{\frac{i-1}{2}}\binom{j-1}{\frac{j-1}{2}} = 2\cdot\facets(G(n-1,i,j))\, .
\]
Also, using Theorem~\ref{thmMninequailty} and the previous cases, we obtain
\[
\begin{split}
    M(n)&amp;\geq 2\cdot M(n-1)
    \\&amp;\geq 2\cdot \facets(G(n-1,i,j))
    \\&amp;= \facets(G(n,i,j)).
\end{split}
\]

Thus, in every case, we have \(\facets(G(n,i,j))\leq M(n)\).
\end{proof}

\section{Graphs with few edges and overlapping cycles}\label{secoverlapcycle}

We next consider the family of graphs on \(n\) vertices and \(n+1\) edges that have two cycles intersecting in at least one edge.
Note that the case where two cycles intersect in exactly one edge was previously studied~\cite[Section 5]{chen2021facets}.
Theorem~\ref{thmMninequailty} allows us to reduce Conjecture~\ref{conjnn1} to the case where \(G\) has no vertices of degree one, as follows.

\begin{corollary}\label{cornoleaves}
If Conjecture~\ref{conjnn1} is true for graphs on \(n\) vertices, then it is true for graphs on \(n+1\) vertices that have at least one leaf.
\end{corollary}

\begin{proof}
Let \(G\) be a graph on \(n+1\) vertices and \(n+2\) edges that has a leaf \(e\). 
Then \(G\setminus\{e\}\) is a graph with \(n\) vertices and \(n+1\) edges, and by assumption \(\facets(G\setminus\{e\})\leq M(n)\).
By Proposition~\ref{propwedgesmultiply} and Theorem~\ref{thmMninequailty}, we get
\[
\facets(G)=2\cdot\facets(G\setminus\{e\})\leq 2\cdot M(n)\leq M(n+1).
\]
\end{proof}


Corollary~\ref{cornoleaves} allows us to restrict our attention to graphs with no leaves. 
Every graph on \(n\) vertices and \(n+1\) edges with no leaves that contains cycles sharing one or more edges can be interpreted as three internally disjoint paths connected at their endpoints. 
We consider these as a special case of a more general construction.

\begin{definition}\label{defgenCB}
For a vector \(\mathbf{m}\in \N^t\), let \(\CB(\mathbf{m})\) denote the graph made of \(t\) internally disjoint paths of lengths \(m_1, m_2,\dots, m_t\) connecting two endpoints.
\end{definition}

Note that when $t=3$, we obtain the leafless connected graphs with $n$ vertices and $n+1$ edges.

\begin{remark}
The graphs \(\CB(\mathbf{m})\) for which all entries of \(\mathbf{m}\) are the same \(m\in \N\) are sometimes called \emph{theta graphs}, denoted by \(\theta_{m,t}\)~\cite{thetagraphs}.
\end{remark}

\begin{proposition}\label{propsameparity}
For \(\mathbf{m}\in \N^t\), we may permute the entries so that without loss of generality we have \(m_1\geq m_2\geq\cdots\geq m_t\).  
If all the \(m_i\)'s have the same parity, then \(\facets(\CB(\mathbf{m}))\) is given by 
\[
F(\mathbf{m})=\sum_{j=0}^{m_t} \binom{m_t}{j}\left[\prod_{k=1}^{t-1}\binom{m_k}{\frac{1}{2}(m_k-m_t)+j}\right].
\]
\end{proposition}

\begin{proof}
Consider \(\CB(\mathbf{m})\) as consisting of paths \(Q_1,Q_2,\dots,Q_t\) having \(m_1\geq \cdots \geq m_t\) edges respectively, as shown in Figure~\ref{figcbgen}.
Since all \(m_i\) are the same parity, it follows that \(\CB(\mathbf{m})\) is bipartite.
For every facet-defining function \(f:V\rightarrow \Z\), we have \(|f(u)-f(v)|=1\) for every edge \(uv\) in \(\CB(\mathbf{m})\)~\cite[Lem.~4.5]{dalidelucchimichalek}. 
If we consider the paths as oriented away from the top vertex toward the bottom vertex, we can view each edge \(u\rightarrow v\) as ascending (\(f(v)-f(u)=1\)) and label it \(1\), or as descending (\(f(v)-f(u)=-1\)) and label it \(-1\).

We count facets by finding \emph{valid} labelings of the edges of \(\CB(\mathbf{m})\) with \(\pm 1\), that is labelings such that the sum of the labels on every path is the same.
For a labeling of a shortest path with length \(m_t\) using \(j\) \((-1)\)s and \(m_t-j\) \(1\)s, the sum of the edge labels is \(m_t-2j\).
There are \(\binom{m_t}{j}\) labelings of this path with this sum.

To produce a valid labeling of the entire graph with each path sum equal to \(m_t-2j\), the number of \((-1)\)s, call this number \(y\), on a path of length \(m_k\) must satisfy the following equation:
\[
\begin{split}
    (+1)(m_k-y)+(-1)y&amp;=m_t-2j\\
    y&amp;=\frac{1}{2}(m_k-m_t)+j.
\end{split}
\]
Thus, there are \(\Ds\binom{m_k}{\frac{1}{2}(m_k-m_t)+j}\) labelings of a path of length \(m_k\) with label sum \(m_t-2j\).  Applying this argument to \(m_k\) for \(k=1,\dots, t-1\) gives
\[
\binom{m_t}{j}\prod_{k=1}^{t-1}\binom{m_k}{\frac{1}{2}(m_k-m_t)+j}
\]
valid labelings of \(\CB(\mathbf{m})\) with \(j\) \((-1)\)s on the shortest path. The result follows by taking the sum over all \(j=0,\dots, m_t\).
\end{proof}

Note that there is a combinatorial interpretation for \(F\), where we consider the arithmetical triangle of binomial coefficients vertically centered at the central terms.
What \(F\) does is select the \(m_t\) row of the arithmetical triangle, multiply each entry by the vertically-aligned entries in rows \(m_1\) through \(m_{t-1}\), and sum the resulting products.

For \(\CB(\mathbf{m})=\theta_{m,t}\) where all the paths are the same length, this formula simplifies.

\begin{corollary}
For \(t\in \N\), we have
\[
\facets(\theta_{m,t})=\sum_{j=0}^m\binom{m}{j}^t.
\]
\end{corollary}

\begin{figure}
\begin{center}
\begin{tikzpicture}
\begin{scope}[scale=1, xshift=0, yshift=0]
	\vertex[fill](a1) at (0,3) {};
	\vertex[fill](a2) at (0,2) {};
	\vertex[fill](a6) at (0,-2) {};
	\vertex[fill](a7) at (0,-3) {};
    \vertex[fill](l2) at (-2,2) {};
	\vertex[fill](l6) at (-2,-2) {};
	\vertex[fill](r2) at (2,2) {};
	\vertex[fill](r6) at (2,-2) {};
	\vertex[label=left:\(Q_{1}\)] (l4) at (-2,1) {};
	\vertex (l5) at (-2,-1) {};
	\vertex[label=left:\(Q_{2}\)] (a4) at (0,1) {};
	\vertex (a5) at (0,-1) {};
	\vertex[label=right:\(Q_{t}\)] (r4) at (2,1) {};
	\vertex (r5) at (2,-1) {};
	\node[] at (1,1) {\(\cdots\)};
	\draw[thick] (a1)--(a2);
	\draw[thick] (a1)--(r2);
	\draw[thick] (a1)--(l2);
	\draw[thick] (a2)--(a4);
	\draw[thick] (r2)--(r4);
	\draw[thick] (l2)--(l4);
	\draw[thick, dotted] (a4)--(a6);
	\draw[thick, dotted] (r4)--(r6);
	\draw[thick, dotted] (l4)--(l6);
	\draw[thick] (a5)--(a6);
	\draw[thick] (r5)--(r6);
	\draw[thick] (l5)--(l6);
	\draw[thick] (a6)--(a7);
	\draw[thick] (a7)--(r6);
	\draw[thick] (a7)--(l6);
\end{scope}
\end{tikzpicture}
\end{center}
\caption{The graph \(\CB(\mathbf{m})\) for \(\mathbf{m}=(m_1,\dots, m_t)\).}
\label{figcbgen}
\end{figure}

If the vector \(\mathbf{m}\) has both even and odd entries, counting the facets of \(\CB(\mathbf{m})\) becomes more complicated, but still involves \(F\).

\begin{proposition}\label{propfacetsofgencbmixed}
For \(\mathbf{m}\in \N^t\), permute the entries so that \(\mathbf{m}=(e_1,\dots, e_k,o_1,\dots, o_\ell)\) with \(e_1\geq e_2\geq\cdots\geq e_k\) even and \(o_1\geq o_2\geq\cdots\geq o_\ell\) odd and \(k,\ell\geq 1\) with \(k+\ell=t\). 
Also, let \(\mathbf{m}_e\) be the vector obtained by subtracting \(1\) from every even entry of \(\mathbf{m}\), and \(\mathbf{m}_o\) the vector obtained by subtracting \(1\) from every odd entry of \(\mathbf{m}\).
\begin{enumerate}
    \item[(i)] If all entries of \(\mathbf{m}\) are at least 2, then
    \[
    \facets(\CB(\mathbf{m})) = \left(\prod_{j=1}^k e_j\right)F(\mathbf{m}_e)+ \left(\prod_{j=1}^\ell o_j\right)F(\mathbf{m}_o).
    \]
    \item[(ii)] If \(o_{p+1}=\cdots=o_\ell=1\) (and \(o_p&gt;1\)), then
    \[
    \facets(\CB(\mathbf{m})) = \left(\prod_{j=1}^k e_j\right)F(\mathbf{m}_e)+ \left(\prod_{j=1}^\ell o_j\right)\facets\left(\left(\bigvee_{j=1}^k C_{e_j}\right)\vee \left(\bigvee_{j=1}^p C_{o_j-1}\right) \right).
    \]
\end{enumerate}
\end{proposition}

\begin{proof}
Consider \(\CB(\mathbf{m})\) as in Figure~\ref{figcbgen}.
As in the proof of Proposition~\ref{propsameparity}, we will count facets of \(P_{\CB(\mathbf{m})}\) by counting valid labelings of the facets subgraphs of \(\CB(\mathbf{m})\).
These subgraphs are those in which either one edge of every even length path has been removed or one edge of every odd length path has been removed.
We can view these as labelings of \(\CB(\mathbf{m})\) where the sum of labels on each \(Q_i\) is equal, and all edges must be labeled with \(\pm 1\) except either
\begin{enumerate}
    \item[A.] one edge on each even path is labeled 0, or
    \item[B.] one edge on each odd path is labeled 0. 
\end{enumerate}
In Case A, there are \(\Ds\prod_{j=1}^k e_j\) ways to choose the edges to label 0.
Having the edge \(uv\) labeled \(0\) indicates that \(f(u)=f(v)\) in the corresponding facet-defining function \(f:V\rightarrow \Z\). 
Thus, we can view this edge as having been contracted since its endpoints have the same value. 
The reduced graph with these edges contracted is \(\CB(\mathbf{m}_e)\), constructed of paths that all have odd length. 
So, by Proposition~\ref{propsameparity}, the number of valid labelings of \(\CB(\mathbf{m})\) where each even path has a \(0\) edge is 
\[
\left(\prod_{j=1}^k e_j\right)F(\mathbf{m}_e).
\]

In Case B, there are \(\Ds\prod_{j=1}^\ell o_j\) ways to choose the edges to label 0. 
If every entry of \(\mathbf{m}\) is at least 2, the graph produced by contracting these \(0\) edges is \(\CB(\mathbf{m}_o)\), constructed of paths that all have even length. 
As above, the number of valid labelings of \(\CB(\mathbf{m})\) of this type is 
\[
\left(\prod_{j=1}^\ell o_j\right)F(\mathbf{m}_o).
\]

Thus, in Case (i) of the Proposition statement, we have 
\[
\facets(\CB(\mathbf{m}))=\left(\prod_{j=1}^k e_j\right)F(\mathbf{m}_e)+\left(\prod_{j=1}^\ell o_j\right)F(\mathbf{m}_o).
\]

To complete Case (ii) of the Proposition, note that if we contract an edge on a path of length \(1\), the endpoints of the remaining paths are identified, and the reduced graph is a wedge of cycles. 
In particular, if \(o_{p+1}=\cdots=o_\ell=1\) and \(o_p&gt;1\), the reduced graph is \(\Ds \left(\bigvee_{j=1}^k C_{e_j}\right)\vee \left(\bigvee_{j=1}^p C_{o_j-1}\right)\). 
Thus, the number of valid labelings of \(\CB(\mathbf{m})\) of this type is 
\[
\facets\left(\left(\bigvee_{j=1}^k C_{e_j}\right)\vee \left(\bigvee_{j=1}^p C_{o_j-1}\right)\right).
\]

Therefore, in Case (ii) of the Proposition, we have
\[
\facets(\CB(\mathbf{m})) = \left(\prod_{j=1}^k e_j\right)F(\mathbf{m}_e)+ \left(\prod_{j=1}^\ell o_j\right)\facets\left(\left(\bigvee_{j=1}^k C_{e_j}\right)\vee \left(\bigvee_{j=1}^p C_{o_j-1}\right) \right).
\]

\end{proof}

Returning to the special case of leafless connected graphs on $n$ vertices with $n+1$ edges, specializing to \(t=3\) provides facet counts for our graphs of interest.

\begin{corollary}\label{corfacetsofcoffeebeans}
The number of facets of the symmetric edge polytope for \(\CB(x_1,x_2,x_3)\) is computed as follows.
\begin{enumerate}
\item[(i)] For \(x_1, x_2, x_3\) either all even or all odd, we have
\[
\facets(\CB(x_1,x_2,x_3))=F(x_1, x_2, x_3)\, .
\]

\item[(ii)] For \(o_1, o_2\) odd and \(e_1\) even, and all at least 2, we have
\[
\facets(\CB(o_1,o_2,e_1))=e_1F(o_1,o_2,e_1-1)+o_1o_2F(o_1-1,o_2-1,e_1)\, .
\]
For \(e_1, e_2\) even and \(o_1\) odd, and all at least 2, we have
\[
\facets(\CB(e_1,e_2,o_1))=o_1F(e_1,e_2,o_1-1)+e_1e_2F(e_1-1,e_2-1,o_1)\, .
\]


\item[(iii)]For \(e_1, e_2\) even and \(o_1=1\), we have
\[
\facets(\CB(e_1,e_2,1))= e_1e_2F(e_1-1,e_2-1,1)+\facets(C_{e_1}\vee C_{e_2}) \, .
\]

\item[(iv)] For \(e_1\) even and \(o_1\geq 3\) odd, we have
\[
\facets(\CB(e_1,o_1,1))=e_1F(e_1-1,o_1,1)+o_1\facets(C_{o_1-1}\vee C_{e_1}) \, .
\]


\item[(v)] For \(e_1\) even, we have
\[
\facets(\CB(e_1,1,1))= e_1F(e_1-1,1,1)+\facets(C_{e_1}) \, .
\]
\end{enumerate}
\end{corollary}


\begin{example}
Figures~\ref{figcbexample0},~\ref{figcbexample1}, and~\ref{figcbexample2} illustrate some of the facet-defining functions for the symmetric edge polytope of \(\CB(4,2,2)\).  The vertices are labeled with their function values, and the edges are labeled ``~\(+\)~" if they are ascending and ``~\(-\)~" if they are descending.
\end{example}

\begin{figure}
\begin{center}
\begin{tikzpicture}
\begin{scope}[scale=.6, xshift=0, yshift=0]

	\vertex[fill,label=above:\(0\)](c1) at (-3,3) {};
	\vertex[fill, label=right:\(1\)] (c2) at (-3,1) {};
	\vertex[fill,label=below:\(2\)] (c3) at (-3,-1) {};
	\vertex[fill, label=left:\(1\)](l1) at (-5,2) {};
	\vertex[fill, label=left:\(2\)](l2) at (-5,1) {};
	\vertex[fill, label=left:\(3\)] (l3) at (-5,0) {};
	\vertex[fill, label=right:\(1\)] (r2) at (-1,1) {};
	\draw[thick] (c1)--(c2) node[pos=.6,right=0.2mm]  {\(+\)};
	\draw[thick] (c1)--(r2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (c1)--(l1) node[pos=.6,above=0.6mm]  {\(+\)}; 
	\draw[thick] (c2)--(c3) node[pos=.4,right=0.2mm]  {\(+\)};
	\draw[thick] (r2)--(c3) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l1)--(l2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l2)--(l3) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l3)--(c3) node[pos=.4,below=0.6mm]  {\(-\)};
	\vertex[fill,label=above:\(0\)](c'1) at (3,3) {};
	\vertex[fill, label=right:\(1\)] (c'2) at (3,1) {};
	\vertex[fill,label=below:\(2\)] (c'3) at (3,-1) {};
	\vertex[fill, label=left:\(1\)](l'1) at (1,2) {};
	\vertex[fill, label=left:\(\phantom{-}2\)](l'2) at (1,1) {};
	\vertex[fill, label=left:\(1\)] (l'3) at (1,0) {};
	\vertex[fill, label=right:\(1\)] (r'2) at (5,1) {};
	\draw[thick] (c'1)--(c'2) node[pos=.6,right=0.2mm]  {\(+\)};
	\draw[thick] (c'1)--(r'2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (c'1)--(l'1) node[pos=.6,above=0.6mm]  {\(+\)}; 
	\draw[thick] (c'2)--(c'3) node[pos=.4,right=0.2mm]  {\(+\)};
	\draw[thick] (r'2)--(c'3) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l'1)--(l'2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l'2)--(l'3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'3)--(c'3) node[pos=.4,below=0.6mm]  {\(+\)};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Some of the facet-defining functions of \(\CB(4,2,2)\) when \(j=0\).}
\label{figcbexample0}
\end{figure}

\begin{figure}
  \begin{center}
\begin{tikzpicture}
\begin{scope}[scale=.6, xshift=0, yshift=0]

	\vertex[fill,label=above:\(0\)](c1) at (-9,3) {};
	\vertex[fill, label=right:\(1\)] (c2) at (-9,1) {};
	\vertex[fill,label=below:\(0\)] (c3) at (-9,-1) {};
	\vertex[fill, label=left:\(1\)](l1) at (-11,2) {};
	\vertex[fill, label=left:\(2\)](l2) at (-11,1) {};
	\vertex[fill, label=left:\(1\)] (l3) at (-11,0) {};
	\vertex[fill, label=right:\(1\)] (r2) at (-7,1) {};
	\draw[thick] (c1)--(c2) node[pos=.6,right=0.2mm]  {\(+\)};
	\draw[thick] (c1)--(r2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (c1)--(l1) node[pos=.6,above=0.6mm]  {\(+\)}; 
	\draw[thick] (c2)--(c3) node[pos=.4,right=0.2mm]  {\(-\)};
	\draw[thick] (r2)--(c3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l1)--(l2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l2)--(l3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l3)--(c3) node[pos=.4,below=0.6mm]  {\(-\)};
    \vertex[fill,label=above:\(0\)](c1) at (-3,3) {};
	\vertex[fill, label=right:\(-1\)] (c2) at (-3,1) {};
	\vertex[fill,label=below:\(0\)] (c3) at (-3,-1) {};
	\vertex[fill, label=left:\(1\)](l1) at (-5,2) {};
	\vertex[fill, label=left:\(2\)](l2) at (-5,1) {};
	\vertex[fill, label=left:\(1\)] (l3) at (-5,0) {};
	\vertex[fill, label=right:\(1\)] (r2) at (-1,1) {};
	\draw[thick] (c'1)--(c'2) node[pos=.6,right=0.2mm]  {\(+\)};
	\draw[thick] (c'1)--(r'2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (c'1)--(l'1) node[pos=.6,above=0.6mm]  {\(+\)}; 
	\draw[thick] (c'2)--(c'3) node[pos=.4,right=0.2mm]  {\(-\)};
	\draw[thick] (r'2)--(c'3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'1)--(l'2) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'2)--(l'3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'3)--(c'3) node[pos=.4,below=0.6mm]  {\(+\)};
	\vertex[fill,label=above:\(0\)](c'1) at (3,3) {};
	\vertex[fill, label=right:\(1\)] (c'2) at (3,1) {};
	\vertex[fill,label=below:\(0\)] (c'3) at (3,-1) {};
	\vertex[fill, label=left:\(1\)](l'1) at (1,2) {};
	\vertex[fill, label=left:\(\phantom{-}0\)](l'2) at (1,1) {};
	\vertex[fill, label=left:\(-1\)] (l'3) at (1,0) {};
	\vertex[fill, label=right:\(1\)] (r'2) at (5,1) {};
	\draw[thick] (c1)--(c2) node[pos=.6,right=0.2mm]  {\(-\)};
	\draw[thick] (c1)--(r2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (c1)--(l1) node[pos=.6,above=0.6mm]  {\(+\)}; 
	\draw[thick] (c2)--(c3) node[pos=.4,right=0.2mm]  {\(+\)};
	\draw[thick] (r2)--(c3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l1)--(l2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l2)--(l3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l3)--(c3) node[pos=.4,below=0.6mm]  {\(-\)};
	\vertex[fill,label=above:\(0\)](c'1) at (9,3) {};
	\vertex[fill, label=right:\(-1\)] (c'2) at (9,1) {};
	\vertex[fill,label=below:\(0\)] (c'3) at (9,-1) {};
	\vertex[fill, label=left:\(1\)](l'1) at (7,2) {};
	\vertex[fill, label=left:\(0\)](l'2) at (7,1) {};
	\vertex[fill, label=left:\(-1\)] (l'3) at (7,0) {};
	\vertex[fill, label=right:\(1\)] (r'2) at (11,1) {};
	\draw[thick] (c'1)--(c'2) node[pos=.6,right=0.2mm]  {\(-\)};
	\draw[thick] (c'1)--(r'2) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (c'1)--(l'1) node[pos=.6,above=0.6mm]  {\(+\)}; 
	\draw[thick] (c'2)--(c'3) node[pos=.4,right=0.2mm]  {\(+\)};
	\draw[thick] (r'2)--(c'3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'1)--(l'2) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'2)--(l'3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'3)--(c'3) node[pos=.4,below=0.6mm]  {\(+\)};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Some of the facet-defining functions of \(\CB(4,2,2)\) when \(j=1\).}
\label{figcbexample1}
\end{figure}

\begin{figure}
  \begin{center}
\begin{tikzpicture}
\begin{scope}[scale=.6, xshift=0, yshift=0]

	\vertex[fill,label=above:\(0\)](c1) at (-3,3) {};
	\vertex[fill, label=right:\(-1\)] (c2) at (-3,1) {};
	\vertex[fill,label=below:\(-2\)] (c3) at (-3,-1) {};
	\vertex[fill, label=left:\(-1\)](l1) at (-5,2) {};
	\vertex[fill, label=left:\(-2\)](l2) at (-5,1) {};
	\vertex[fill, label=left:\(-3\)] (l3) at (-5,0) {};
	\vertex[fill, label=right:\(-1\)] (r2) at (-1,1) {};
	\draw[thick] (c1)--(c2) node[pos=.6,right=0.2mm]  {\(-\)};
	\draw[thick] (c1)--(r2) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (c1)--(l1) node[pos=.6,above=0.6mm]  {\(-\)}; 
	\draw[thick] (c2)--(c3) node[pos=.4,right=0.2mm]  {\(-\)};
	\draw[thick] (r2)--(c3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l1)--(l2) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l2)--(l3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l3)--(c3) node[pos=.4,below=0.6mm]  {\(+\)};
	\vertex[fill,label=above:\(0\)](c'1) at (4,3) {};
	\vertex[fill, label=right:\(-1\)] (c'2) at (4,1) {};
	\vertex[fill,label=below:\(-2\)] (c'3) at (4,-1) {};
	\vertex[fill, label=left:\(-1\)](l'1) at (2,2) {};
	\vertex[fill, label=left:\(-2\)](l'2) at (2,1) {};
	\vertex[fill, label=left:\(-1\)] (l'3) at (2,0) {};
	\vertex[fill, label=right:\(-1\)] (r'2) at (6,1) {};
	\draw[thick] (c'1)--(c'2) node[pos=.6,right=0.2mm]  {\(-\)};
	\draw[thick] (c'1)--(r'2) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (c'1)--(l'1) node[pos=.6,above=0.6mm]  {\(-\)}; 
	\draw[thick] (c'2)--(c'3) node[pos=.4,right=0.2mm]  {\(-\)};
	\draw[thick] (r'2)--(c'3) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'1)--(l'2) node[pos=.5,right=0.2mm]  {\(-\)};
	\draw[thick] (l'2)--(l'3) node[pos=.5,right=0.2mm]  {\(+\)};
	\draw[thick] (l'3)--(c'3) node[pos=.4,below=0.6mm]  {\(-\)};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{Some of the facet-defining functions of \(\CB(4,2,2)\) when \(j=2\).}
\label{figcbexample2}
\end{figure}

Using these results, we can make partial progress toward Conjecture~\ref{conjnn1} in two special cases, given below in Theorem~\ref{thmgeneralFlessthanM} and Proposition~\ref{propmaxCBlessthanM}.

\begin{theorem}{\label{thmgeneralFlessthanM}}
For all \(n\geq 4\), if \(x_1\geq x_2\geq x_3\geq 1\), all \(x_i\)'s have the same parity, and \(x_1+x_2+x_3=n+1\), then
\[
F(x_1,x_2,x_3)\leq M(n).
\]
Thus, if \(x_1, x_2, x_3\) are all of the same parity, then Conjecture~\ref{conjnn1} is true.
\end{theorem}

\begin{remark}
The proof of Theorem~\ref{thmgeneralFlessthanM} makes use of the Stirling bounds on \(n!\)~\cite{robbins1955stirling}: 
\[
\sqrt{2\pi}\phantom{\cdot}n^{n+\frac{1}{2}}e^{-n}e^\frac{1}{12n+1}\leq n!\leq \sqrt{2\pi}\phantom{\cdot}n^{n+\frac{1}{2}}e^{-n}e^\frac{1}{12n}
\]
\end{remark}

\begin{proof}[Proof of Theorem~\ref{thmgeneralFlessthanM}]
In each of the following cases, we show that the desired inequality holds for large enough \(n\).
For all smaller values of \(n\) we have verified that the theorem holds using SageMath~\cite{sage}. 
Throughout the proof, we use the notation \(\overset{!}{\leq}\) to indicate an unproven inequality we wish to show.

\noindent\emph{Case 1:} Assume \(n=2k-1\).
In this case, we have \(x_1+x_2+x_3=2k\) and all \(x_i\)'s are even by assumption.
Thus, we have
\[
\begin{split}
  F(x_1,x_2,x_3)&amp;=\sum_{j=0}^{x_3}\binom{x_3}{j}\binom{x_2}{\frac{1}{2}\left(x_2-x_3\right)+j}\binom{x_1}{\frac{1}{2}\left(x_1-x_3\right)+j}\\
  &amp;\leq (x_3+1)\binom{x_3}{\frac{x_3}{2}}\binom{x_2}{\frac{x_2}{2}}\binom{x_1}{\frac{x_1}{2}}.
\end{split}
\]

\emph{Subcase 1(a):} If \(k\) is even, then
\[
M(n)=M(2k-1)=(k+1)(k-1)\binom{k}{\frac{k}{2}}\binom{k-2}{\frac{k-2}{2}}.
\]
To show \(F(x_1,x_2,x_3)\leq M(n)\), it suffices to show
\begin{equation}\label{ineqWTScase1a}
\begin{split}
    (x_3+1)\phantom{\cdot}x_3!x_2!x_1!\left(\frac{k}{2}!\right)^2\left(\frac{k-2}{2}!\right)^2\overset{!}{\leq} (k+1)(k-1)k!(k-2)!\left(\frac{x_3}{2}!\right)^2\left(\frac{x_2}{2}!\right)^2\left(\frac{x_1}{2}!\right)^2.
    \end{split}
\end{equation}
By the Stirling bounds on \(n!\), it suffices to show that

\[
\begin{pmatrix}
(x_3+1)x_3^{x_3+\frac{1}{2}}x_2^{x_2+\frac{1}{2}}x_1^{x_1+\frac{1}{2}} &amp;
\\&amp;
\\\cdot \left(\frac{k}{2}\right)^{k+1}\left(\frac{k-2}{2}\right)^{k-1} &amp;
\\&amp;
\\ \cdot e^{-(x_1+x_2+x_3+2k)+2} &amp;
\\&amp;
\\ \cdot e^{\frac{1}{12x_3}+\frac{1}{12x_2}+\frac{1}{12x_1}+\frac{1}{3k}+\frac{1}{3(k-2)}} &amp;
\end{pmatrix}
\overset{!}{\leq} 
\begin{pmatrix}
&amp;\sqrt{2\pi}\left(\frac{x_3}{2}\right)^{x_3+1}\left(\frac{x_2}{2}\right)^{x_2+1}\left(\frac{x_1}{2}\right)^{x_1+1}
\\&amp;
\\&amp;\cdot (k+1)(k-1)k^{k+\frac{1}{2}}(k-2)^{k-\frac{3}{2}}
\\&amp;
\\&amp;\cdot e^{-(x_1+x_2+x_3+2k)+2}
\\&amp;
\\&amp;\cdot e^{\frac{1}{12k+1}+\frac{1}{12k-23}+ \frac{2}{6x_3+1}+ \frac{2}{6x_2+1}+ \frac{2}{6x_1+1}}
\end{pmatrix}
\]

or, equivalently, to show that
\[
\begin{pmatrix}
    (x_3+1)&amp;
    \\&amp;
    \\\cdot k^{k+1}(k-2)^{k-1}&amp;
    \\&amp;
    \\\cdot e^{\frac{1}{12x_3}+\frac{1}{12x_2}+\frac{1}{12x_1}+\frac{1}{3k}+\frac{1}{3(k-2)}}&amp;
\end{pmatrix}
    \overset{!}{\leq}
\begin{pmatrix}
    &amp;\frac{\sqrt{2\pi}}{8}\sqrt{x_1x_2x_3}
    \\&amp;
    \\&amp;\cdot (k+1)(k-1)k^{k+\frac{1}{2}}(k-2)^{k-\frac{3}{2}}
    \\&amp;
    \\&amp;\cdot e^{\frac{1}{12k+1}+\frac{1}{12k-23}+ \frac{2}{6x_3+1}+ \frac{2}{6x_2+1}+ \frac{2}{6x_1+1}}
\end{pmatrix}.
\]

Since \(\frac{1}{12k+1}+\frac{1}{12k-23}&gt; 0\) for \(k\geq 2\), we have
\[
e^{\frac{1}{12k+1}+\frac{1}{12k-23}} &gt; 1.
\]
Also, since
\[
-1\leq \frac{1}{12x}-\frac{2}{6x+1} \leq 0
\]
for all \(x\geq 1\), we have
\[
0\leq e^{\frac{1}{12x_3}-\frac{2}{6x_3+1}+\frac{1}{12x_2}-\frac{2}{6x_2+1}+\frac{1}{12x_1}-\frac{2}{6x_1+1}}\leq 1
\]
for all \(x_1,x_2,x_3\).
Therefore, to show inequality~\eqref{ineqWTScase1a}, it suffices to show 
\[
 (x_3+1)k^{k+1}(k-2)^{k-1}e^{\frac{1}{3k}+\frac{1}{3(k-2)}}\overset{!}{\leq}\frac{\sqrt{2\pi}}{8}(k+1)(k-1)k^{k+\frac{1}{2}}(k-2)^{k-\frac{3}{2}}\sqrt{x_1x_2x_3}
\]
or, rather, to show

\[
 (x_3+1)\sqrt{k(k-2)}e^{\frac{1}{3k}+\frac{1}{3(k-2)}}\overset{!}{\leq}\frac{\sqrt{2\pi}}{8}(k+1)(k-1)\sqrt{x_1x_2x_3}.
\]

Finally, we note the following:
\begin{itemize}
    \item By assumption, we have \(\Ds x_3+1\leq\frac{2k}{3}+1\leq k+1\), and thus \(\Ds\frac{x_3+1}{k+1}\leq 1\).
    \item We have \(\Ds\frac{\sqrt{k(k-2)}}{k-1}\leq 1\).
    \item We have \(\Ds 0&lt; e^{\frac{1}{3k}+\frac{1}{3(k-2)}} &lt; e\) for \(k\geq 3\).
    \item By assumption, we have \(\Ds x_1\geq \frac{2k}{3}\), and \(x_2,x_3\geq 2\), implying that \(\Ds x_1x_2x_3\geq \frac{8k}{3}\). 
\end{itemize}

With this, it suffices to show that
\[
e\overset{!}{\leq} \frac{\sqrt{2\pi}}{8}\sqrt{\frac{8k}{3}}
\]
or, equivalently, that
\[
k\overset{!}{\geq} \frac{12e^2}{\pi}\approx 28.224.
\]
This inequality and the desired inequality hold for all even \(k\geq 30\).


\emph{Subcase 1(b):} If \(k\) is odd, then
\[
M(n)=M(2k-1)=k^2\binom{k-1}{\frac{k-1}{2}}.
\]

To show \(F(x_1,x_2,x_3)\leq M(n)\), it suffices to show
\begin{equation}\label{ineqWTScase1b}
\begin{split}
    (x_3+1)\phantom{\cdot}x_3!x_2!x_1!\left(\frac{k-1}{2}!\right)^4\overset{!}{\leq} (k!)^2\left(\frac{x_3}{2}!\right)^2\left(\frac{x_2}{2}!\right)^2\left(\frac{x_1}{2}!\right)^2.
    \end{split}
\end{equation}

By the Stirling bounds on \(n!\), it suffices to show
\[
\begin{pmatrix}
(x_3+1)x_3^{x_3+\frac{1}{2}}x_2^{x_2+\frac{1}{2}}x_1^{x_1+\frac{1}{2}}&amp;
\\&amp;
\\\cdot\left(\frac{k-1}{2}\right)^{2k}&amp;
\\&amp;
\\\cdot e^{-(x_1+x_2+x_3+2k)+2}&amp;
\\&amp;
\\\cdot e^{\frac{1}{12x_3}+\frac{1}{12x_2}+\frac{1}{12x_1}+\frac{2}{3(k-1)}}
\end{pmatrix}
    \overset{!}{\leq} 
\begin{pmatrix}
&amp;\sqrt{2\pi}\left(\frac{x_3}{2}\right)^{x_3+1}\left(\frac{x_2}{2}\right)^{x_2+1}\left(\frac{x_1}{2}\right)^{x_1+1}
\\&amp;
\\&amp;\cdot k^{2k+1}
\\&amp;
\\&amp;\cdot e^{-(x_1+x_2+x_3+2k)}
\\&amp;
\\&amp;\cdot e^{\frac{2}{12k+1}+ \frac{2}{6x_3+1}+ \frac{2}{6x_2+1}+ \frac{2}{6x_1+1}}
\end{pmatrix}.
\]
Using the same kinds of computations as the previous case, we see it suffices to show
\[
e^2(x_3+1)(k-1)^{2k}e^{\frac{2}{3(k-1)}}\overset{!}{\leq} \frac{\sqrt{2\pi}}{8}k^{2k+1}\sqrt{x_1x_2x_3}.
\]

Now note the following:
\begin{itemize}
    \item We have \(\Ds x_3+1\leq \frac{2k}{3}+1\leq k\) for \(k\geq 3\) and thus \(\frac{x_3+1}{k}\leq 1\).
    \item We have \(\Ds e^2\left(\frac{k-1}{k}\right)^{2k}\leq 1\) for \(k\geq 3\).
    \item We have \(1\leq e^{\frac{2}{3(k-1)}}\leq e\) for \(k\geq 2\).
\end{itemize}
So, it suffices to show that
\[
e\overset{!}{\leq}\frac{\sqrt{2\pi}}{8}\sqrt{x_1x_2x_3}, 
\]
which, as before, holds for 
\[
k\geq \frac{12e^2}{\pi}\approx 28.224 
\]
or all odd \(k\geq 29\).

\noindent\emph{Case 2:} Assume \(n=2k\).
In this case, we have \(x_1+x_2+x_3=2k+1\) and all \(x_i\)'s are odd by assumption.
Thus, we have
\[
\begin{split}
    F(x_1,x_2,x_3)&amp;=\sum_{j=0}^{x_3}\binom{x_3}{j}\binom{x_2}{\frac{1}{2}\left(x_2-x_3\right)+j}\binom{x_1}{\frac{1}{2}\left(x_1-x_3\right)+j}\\&amp;\leq (x_3+1)\binom{x_3}{\frac{x_3-1}{2}}\binom{x_2}{\frac{x_2-1}{2}}\binom{x_1}{\frac{x_1-1}{2}}.
\end{split}
\]

\emph{Subcase 2(a):} If \(k\) is even, then
\[
M(n)=M(2k)=2(k+1)(k-1)\binom{k}{\frac{k}{2}}\binom{k-2}{\frac{k-2}{2}}.
\]
To show \(F(x_1,x_2,x_3)\leq M(n)\), it suffices to show
\begin{equation}\label{ineqWTScase2a}
\begin{split}
  &amp;(x_3+1)\phantom{\cdot}x_3!x_2!x_1!\left(\frac{k}{2}!\right)^2\left(\frac{k-2}{2}!\right)^2\\
  &amp;\overset{!}{\leq} 2(k+1)(k-1)k!(k-2)! \prod_{k=1}^3\left[\left(\frac{x_i+1}{2}!\right)\left(\frac{x_i-1}{2}!\right)\right]\, .
    \end{split}
\end{equation}
Equivalently, we want
\[
\begin{split}
  &amp;(x_3+1)\phantom{\cdot}x_3!x_2!x_1!\left(\frac{k}{2}!\right)^2\left(\frac{k-2}{2}!\right)^2\\
  &amp;\overset{!}{\leq} 2(k+1)(k-1)k!(k-2)!\prod_{i=1}^3\left(\frac{x_i+1}{2}!\right)^2\left(\frac{8}{(x_3+1)(x_2+1)(x_1+1)}\right),
\end{split}
\]
or, equivalently, we want
\[
\begin{split}
&amp;(x_3+1)\phantom{\cdot}(x_3+1)!(x_2+1)!(x_1+1)!\left(\frac{k}{2}!\right)^2\left(\frac{k-2}{2}!\right)^2\\&amp;\overset{!}{\leq} 16(k+1)(k-1)k!(k-2)!\left(\frac{x_3+1}{2}!\right)^2\left(\frac{x_2+1}{2}!\right)^2\left(\frac{x_1+1}{2}!\right)^2.
\end{split}
\]

By the Stirling bounds, it suffices to show
\begin{align*}
  &amp;
\begin{pmatrix}
    (x_3+1)(x_3+1)^{x_3+\frac{3}{2}}(x_2+1)^{x_2+\frac{3}{2}}(x_1+1)^{x_1+\frac{3}{2}}\left(\frac{k}{2}\right)^{k+1}\left(\frac{k-2}{2}\right)^{k-1}&amp;
    \\&amp;
    \\\cdot \, e^{-(x_3+x_2+x_1+2k+1)}e^{\frac{1}{12(x_3+1)}+\frac{1}{12(x_2+1)}+\frac{1}{12(x_1+1)}+\frac{1}{3k}+\frac{1}{3(k-2)}}
  \end{pmatrix}    \\
    \overset{!}{\leq}&amp;  
\begin{pmatrix}
    &amp; 16\sqrt{2\pi}\left(\frac{x_3+1}{2}\right)^{x_3+2}\left(\frac{x_2+1}{2}\right)^{x_2+2}\left(\frac{x_1+1}{2}\right)^{x_1+2} (k+1)(k-1)k^{k+\frac{1}{2}}(k-1)^{k-\frac{3}{2}}
    \\&amp;
    \\&amp;\cdot \, e^{-(x_3+x_2+x_1+2k+1)}e^{\frac{1}{12k+1}+\frac{1}{12(k-2)+1}+\frac{2}{6(x_3+1)+1}+\frac{2}{6(x_2+1)+1}+\frac{2}{6(x_1+1)+1}}
\end{pmatrix}.
\end{align*}
After computations similar to those in Case~1, we see it suffices to show
\[
(x_3+1)\sqrt{k(k-2)}e\overset{!}{\leq} \frac{\sqrt{2\pi}}{8}(k+1)(k-1)\sqrt{(x_1+1)(x_2+1)(x_3+1)}
\]
where \(x_1+1\geq \frac{2k+4}{3}\) and \(x_2+1\geq 2\) and \(x_3+1\geq 2\).
It therefore suffices to show 
\[
e\overset{!}{\leq}\frac{\sqrt{2\pi}}{8}\sqrt{4\left(\frac{2k+4}{3}\right)}
\]
or, equivalently, to have
\[
k\geq \frac{12e^2}{\pi}-2\approx 26.224.
\]
Thus, the desired inequality holds for even \(k\geq 28\).

\emph{Subcase 2(b):} If \(k\) is odd, then

\[
M(n)=M(2k)=2k^2\binom{k-1}{\frac{k-1}{2}}^2.
\]

To show \(F(x_1,x_2,x_3)\leq M(n)\), it suffices to show

\begin{equation}
\begin{split}
    &amp;(x_3+1)x_3!x_2!x_1!\left(\frac{k-1}{2}!\right)^4\\&amp;\overset{!}{\leq} 2(k!)^2\left(\frac{x_3-1}{2}!\right)\left(\frac{x_3+1}{2}!\right)\left(\frac{x_2-1}{2}!\right)\left(\frac{x_2+1}{2}!\right)\left(\frac{x_1-1}{2}!\right)\left(\frac{x_1+1}{2}!\right).
    \end{split}
\end{equation}

Equivalently, we want

\[
\begin{split}
 &amp;(x_3+1)\phantom{\cdot}x_3!x_2!x_1!\left(\frac{k-1}{2}!\right)^4
 \\&amp;\overset{!}{\leq} 2(k!)^2\left(\frac{x_3+1}{2}!\right)^2\left(\frac{x_2+1}{2}!\right)^2\left(\frac{x_1+1}{2}!\right)^2\left(\frac{8}{(x_3+1)(x_2+1)(x_1+1)}\right),   
\end{split}
\]

which is equivalent to

\[
\begin{split}
    &amp;(x_3+1)(x_3+1)!(x_2+1)!(x_1+1)!\left(\frac{k-1}{2}!\right)^4
    \\&amp;\overset{!}{\leq} 16(k!)^2\left(\frac{x_3+1}{2}!\right)^2\left(\frac{x_2+1}{2}!\right)^2\left(\frac{x_1+1}{2}!\right)^2.
\end{split}
\]

By the Stirling bounds, it suffices to show
\begin{align*}
 &amp;
\begin{pmatrix}
    (x_3+1)(x_3+1)^{x_3+\frac{3}{2}}(x_2+1)^{x_2+\frac{3}{2}}(x_1+1)^{x_1+\frac{3}{2}}\left(\frac{k-1}{2}\right)^{2k}&amp;
    \\&amp;
    \\\cdot \, e^{-(x_3+x_2+x_1+2k+1)}e^{\frac{1}{12(x_3+1)}+\frac{1}{12(x_2+1)}+\frac{1}{12(x_1+1)}+\frac{2}{3(k-1)}}
  \end{pmatrix} \\
    \overset{!}{\leq} &amp;
\begin{pmatrix}    
    &amp;16\sqrt{2\pi}\phantom{\cdot}\left(\frac{x_3+1}{2}\right)^{x_3+2}\left(\frac{x_2+1}{2}\right)^{x_2+2}\left(\frac{x_1+1}{2}\right)^{x_1+2}k^{2k+1}
    \\&amp;
    \\&amp;\cdot \, e^{-(x_3+x_2+x_1+2k+3)}e^{\frac{2}{12k+1}+\frac{2}{6(x_3+1)+1}+\frac{2}{6(x_2+1)+1}+\frac{2}{6(x_1+1)+1}}
\end{pmatrix}.
\end{align*}

After computations similar to those in previous cases, we see it suffices to show
\[
e^2(x_3+1)(k-1)^{2k}e^{\frac{2}{3(k-1)}}\overset{!}{\leq}\frac{\sqrt{2\pi}}{8}k^{2k+1}\sqrt{(x_1+1)(x_2+1)(x_3+1)} \, .
\]

Similar to Case 1, it suffices to show that
\[
e\overset{!}{\leq}\frac{\sqrt{2\pi}}{8}\sqrt{(x_1+1)(x_2+1)(x_3+1)}
\]
with \(x_1+1\geq \frac{2k+4}{3}\) and \(x_2+1\geq 2\) and \(x_3+1\geq 2\).
Thus, the desired inequality holds for 
\[
k\geq \frac{12e^2}{\pi}-2\approx 26.224,
\]
hence all odd \(k\geq 27\).
\end{proof}

Our second special case concerns a certain family of \(\CB\) graphs with an even number of vertices where the two cycles share exactly one edge.
We will need the following lemma, the proof of which follows from straightforward computations after expanding the right hand sides below. 

\begin{lemma}\label{lemauxeqs}
\noindent If \(k\) is even, then
    \begin{equation}\label{eqnevenMandFequalityfirst}
    M(2k)=\left(\frac{k+2}{2}\right)\left(\frac{k}{2}\right)F(k+1,k-1,1).
    \end{equation}
If \(k\) is odd, then
    \begin{equation}\label{eqnevenMandFequalitysecond}
    M(2k)=\left(\frac{k+1}{2}\right)^2F(k,k,1).
    \end{equation}
For even \(k\), we have
\begin{equation}\label{eqnMincrementingequalityeven}
M(2k-2)=\frac{k}{2(k+1)}M(2k-1).
\end{equation} 
For odd \(k\), we have
\begin{equation}\label{eqnMincrementingequalityodd}
M(2k-2)=\frac{k-1}{2k}M(2k-1).
\end{equation}
For all \(k\), we have
\begin{equation}\label{eqnMincrementingequalityall}
M(2k-1)=\frac{1}{2}M(2k).
\end{equation}
Finally, if \(k\) is even, then
\begin{equation}\label{eqnNcycleequality}
\facets(C_k)=\frac{4}{k}\facets(C_{k-1}) \, .
\end{equation}
\end{lemma}


\begin{proposition}\label{propmaxCBlessthanM}
Let \(n=2k\geq 10\).
\begin{enumerate}
    \item[(i)] If \(k\) is even, then
    \[
    \facets(\CB(k,k,1))\leq M(2k).
    \]
    \item[(ii)] If \(k\) is odd, then
    \[
    \facets(\CB(k+1,k-1,1))\leq M(2k).
    \]
\end{enumerate}
\end{proposition}

\begin{proof}
For even \(k\), we have
\[
\begin{split}
    \facets(\CB(k,k,1))&amp;=\facets(C_k\vee C_k)+k^2F(k-1,k-1,1)
    \\&amp;\overset{\eqref{eqnNcycleequality}, \eqref{eqnevenMandFequalitysecond}}{=}\frac{16}{k^2}\facets(C_{k-1}\vee C_{k-1})+\frac{4k^2}{k^2}M(2k-2)
    \\&amp;\overset{\mathrm{Def}~\ref{defMn}}{=}\frac{16}{k^2}M(2k-3)+4M(2k-2)
    \\&amp;\overset{\eqref{eqnMincrementingequalityall},\eqref{eqnMincrementingequalityeven}}{=}\frac{2}{k(k+1)}M(2k)+\frac{k-1}{k}M(2k)
    \\&amp;=\frac{k^2+1}{k^2+k}M(2k)\leq M(2k).
\end{split}
\]

For odd \(k\), we have
\[
\begin{split}
    \facets(\CB(k+1,k-1,1))&amp;=\facets(C_{k+1}\vee C_{k-1})+k^2F(k-1,k-1,1)
    \\&amp;\overset{\eqref{eqnNcycleequality},\, \eqref{eqnevenMandFequalityfirst}}{=}\frac{16}{(k+1)(k-1)}\facets(C_{k}\vee C_{k-2})+\frac{4(k+1)(k-1)}{(k+1)(k-1)}M(2k-2)
    \\&amp;\overset{\mathrm{Def}~\ref{defMn}}{=}\frac{16}{(k+1)(k-1)}M(2k-3)+4M(2k-2)
    \\&amp;\overset{\eqref{eqnMincrementingequalityall},\eqref{eqnMincrementingequalityodd}}{=}\frac{2}{k(k+1)}M(2k)+\frac{k}{k+1}M(2k)
    \\&amp;=\frac{k^2+2}{k^2+k}M(2k)\leq M(2k).
\end{split}
\]
\end{proof}

\section{Further conjectures and open problems}\label{secconjectures}

Through the course of this study, we observed several patterns that remain as conjectures and open questions.
First, computational evidence suggests interesting structure for the function \(F(x_1,x_2,x_3)\) beyond Theorem~\ref{thmgeneralFlessthanM}.
We formally record our observations as the following conjecture, which has been confirmed with SageMath~\cite{sage} for all $n$ less than or equal to $399$.

\begin{conjecture}\label{conjFbounds}
For \(n=2k\) and \(k\geq 2\) with \(x_1+x_2+x_3=n+1\), the function \(F(x_1,x_2,x_3)\) is maximized at \(F(n-1,1,1)\).
For \(n=2k-1\) and \(k\geq 3\) with \(x_1+x_2+x_3=n+1\), the function \(F(x_1,x_2,x_3)\) is maximized at \(F(n-3,2,2)\).
Further, for every \(x_1\geq x_2\geq x_3\geq 3\) all even or all odd positive integers, we have
\[
F(x_1,x_2,x_3)\leq F(x_1+2,x_2,x_3-2)
\]
and
\[
F(x_1,x_2,x_3)\leq F(x_1+2,x_2-2,x_3) \, ,
\]
when the subtraction by \(2\) will maintain the inequalities on the \(x_i\)'s.
\end{conjecture}

For example, the first inequality in Conjecture~\ref{conjFbounds} asserts that for $x_1\geq x_2 \geq x_3\geq 5$ all of the same parity,
\begin{align*}
&amp; \sum_{j=0}^{x_3}\binom{x_3}{j}\binom{x_2}{\frac{1}{2}\left(x_2-x_3\right)+j}\binom{x_1}{\frac{1}{2}\left(x_1-x_3\right)+j}\\
\leq &amp; \sum_{j=0}^{x_3-2}\binom{x_3-2}{j}\binom{x_2}{\frac{1}{2}\left(x_2-x_3+2\right)+j}\binom{x_1+2}{\frac{1}{2}\left(x_1-x_3\right)+j} \, .
\end{align*}

Second, the remaining case for Conjecture~\ref{conjnn1} is the following.

\begin{conjecture}\label{conjremainingcb}
If \(x_1\), \(x_2\), and \(x_3
\) have different parities, then \(N(\CB(x_1,x_2,x_3))\leq M(n)\).
\end{conjecture}

Using the recursion given by Corollary~\ref{corfacetsofcoffeebeans} and the inequality \(x_i\leq n\), it is straightforward to deduce that \(N(\CB(x_1,x_2,x_3))\leq 6n^2M(n)\).
It is not clear to the authors how to obtain a stronger bound in this case.
One direction toward proving Conjecture~\ref{conjremainingcb} is the following.

\begin{conjecture}\label{conjMixedparityCBmaximizers}
For \(n\geq 10\), the value \(\facets(\CB(x_1,x_2,x_3))\) with \(x_1+x_2+x_3=n+1\) is maximized by
\[
\begin{cases}
\CB(k-1,k-1,2), &amp; \text{if $n=2k-1$ and \(k\) even;}\\
\CB(k,k-2,2), &amp; \text{if $n=2k-1$ and \(k\) odd;}\\
\CB(k,k,1), &amp; \text{if $n=2k$ and \(k\) even;}\\
\CB(k+1,k-1,1), &amp; \text{if $n=2k$ and \(k\) odd.}\\
\end{cases}
\]
\end{conjecture}

Using SageMath~\cite{sage}, we have computed \(\facets(\CB(x_1,x_2,x_3))\) for all tuples with \(x_1+x_2+x_3=n+1\leq 535\). 
All of these values are less than or equal to the number of facets of our conjectured maximizer for the corresponding \(n\), providing significant support for Conjecture~\ref{conjMixedparityCBmaximizers}.

Third, when \(n\) is even, Proposition~\ref{propmaxCBlessthanM} gives that the number of facets given by these conjectured maximizing graphs remains less than \(M(n)\). 
Currently, for odd \(n\) we do not know of an equality or a bound strong enough to accomplish what~\eqref{eqnevenMandFequalityfirst}~and~\eqref{eqnevenMandFequalitysecond} give for even \(n\). 
Therefore, a similar result for odd \(n\) remains unproven.
We have verified that such a result holds for all odd \(n\) less than 100,000 via computations with SageMath~\cite{sage}.

Fourth and finally, throughout our investigations we sought examples of graphs having a high number of symmetric edge polytope facets. Conjecture~\ref{conjmaxmin} asserts that graphs appearing as global facet-maximizers for connected graphs on $n$ vertices can be constructed from minimally intersecting odd cycles, but it is unclear how to prove this.
A related problem would be to prove that the graphs appearing as global facet-maximizers in Conjecture~\ref{conjmaxmin} are facet-maximizers among connected graphs having a fixed number of edges.
We explore this idea a bit further in the special case of the following graphs, which are the conjectured global facet-maximizers for connected graphs on an odd number of vertices.

\begin{definition}
Let \(\windmill(n,r)\) denote the \emph{windmill} graph on \(n\) vertices consisting of \(r\) copies of the cycle \(C_3\) and \(n-1-2r\) edges all wedged at a single vertex.
We say a windmill is \emph{full} if \(n\) is odd and \(r=\frac{n-1}{2}\).
In other words, a full windmill is a wedge of \(\frac{n-1}{2}\) triangles at a single vertex.
Denote by \(\windmill(n)\) the full windmill on \(n\) vertices.
\end{definition}

 \begin{figure}
\begin{center}
    \begin{tikzpicture}
    
    \begin{scope}[scale=1, xshift=0, yshift=0]
	\vertex[fill](v1) at (0,0) {};
	\vertex[fill](v2) at (0,1.5) {};
	\vertex[fill](v3) at (1.25,.75) {};
	\vertex[fill](v4) at (1.25,-.75) {};
	\vertex[fill](v5) at (0,-1.5) {};	
	\vertex[fill](v6) at (-1.25,-.75) {};
	\vertex[fill](v7) at (-1.25,.75) {};	
	\draw[thick] (v1)--(v2);
	\draw[thick] (v1)--(v3);
	\draw[thick] (v1)--(v4);
	\draw[thick] (v1)--(v5);	
	\draw[thick] (v1)--(v6);
	\draw[thick] (v1)--(v7);
	\draw[thick] (v2)--(v3);
	\draw[thick] (v4)--(v5);
    \node[] at (-2.5,1) {\(\windmill(7,2)\)};   
    \end{scope}
    
    
    \begin{scope}[scale=1, xshift=200, yshift=0]
	\vertex[fill](v1) at (0,0) {};
	\vertex[fill](v2) at (0,1.5) {};
	\vertex[fill](v3) at (1.25,.8) {};
	\vertex[fill](v4) at (1.25,-.3) {};
	\vertex[fill](v5) at (.55,-1.35) {};	
	\vertex[fill](v6) at (-1.25,-.5) {};
	\vertex[fill](v7) at (-1.25,.8) {};
	\vertex[fill](v8) at (-0.6, -1.35) {};
	\draw[thick] (v1)--(v2);
	\draw[thick] (v1)--(v3);
	\draw[thick] (v1)--(v4);
	\draw[thick] (v1)--(v5);	
	\draw[thick] (v1)--(v6);
	\draw[thick] (v1)--(v7);
	\draw[thick] (v1)--(v8);
 	\draw[thick] (v2)--(v3);
 	\draw[thick] (v4)--(v5);
    \node[] at (-2.5,1) {\(\windmill(8,2)\)}; 
    \end{scope}    
    \end{tikzpicture}    
\end{center}
    \caption{Two windmill graphs which are not full.}
    \label{figwindmills}
\end{figure}


\begin{proposition}
For all odd \(n\), we have 
\[
\facets(\windmill(n))=6^{\frac{n-1}{2}}
\]
\end{proposition}

\begin{proof}
The windmill \(\windmill(n)\) is a join of \(\frac{n-1}{2}\) 3-cycles.  By Lemma~\ref{lemcyclefacets} and Proposition~\ref{propwedgesmultiply}, we obtain
\[
\facets(\windmill(n))=\left(\facets(C_3)\right)^{\frac{n-1}{2}}=6^{\frac{n-1}{2}}.
\]
\end{proof}

\begin{conjecture}\label{conjwindmill}
  For odd \(n\), among graphs with \(n\) vertices and \(3(n-1)/2\) edges, $\windmill(n)$ is a facet-maximizer.
\end{conjecture}

To support this conjecture, we used SageMath~\cite{sage} to sample the space of connected graphs with \(n\) vertices and \(3(n-1)/2\) edges using a Markov Chain Monte Carlo technique~\cite[Section~2]{SIAMMCMC}.
We then computed \(\facets(\PG)\) for each graph \(G\) in our sample.
The transition operation we consider is an edge replacement.
Starting at a graph \(G\), we produce a new graph \(G'\) by randomly choosing an edge \(e\in E(G)\) and a non-edge \(f\in E(G)^C\).
Then, if the edges \((E(G)\setminus\{e\})\cup\{f\}\) form a connected graph, define \(G'\) to be this graph. 
If the new graph is not connected, let \(G'=G\) (in other words, sample at \(G\) again).

Using this single-edge replacement, the resulting graph of graphs \(\mathcal{G}\) is regular~\cite{SIAMMCMC}, with each node having in-degree and out-degree both equal to
\[
  \frac{3}{2}(n-1)\left(\binom{n}{2}-\frac{3}{2}(n-1)\right)\, .
\]
Given two graphs \(G_1\) and \(G_2\) in the space, there is a sequence of edge replacements that first transforms a spanning tree of \(G_1\) into a spanning tree of \(G_2\) and then replaces all other edges in \(E(G_1)\setminus E(G_2)\) with edges in \(E(G_2)\setminus E(G_1)\) in some order.  
Thus \(G_2\) is reachable from \(G_1\) and hence \(G_1\) is reachable from \(G_2\) since all edge replacements are reversible.
Thus \(\mathcal{G}\) is strongly connected.
Finally, it is straightforward to see that \(\mathcal{G}\) is aperiodic, as it contains 2-cycles and 3-cycles.
Thus, we can conclude that samples from this Markov chain asymptotically obey a uniform distribution, and we can assume that this process uniformly samples the space of connected graphs with \(n\) vertices and \(3(n-1)/2\) edges.
We generated sample families of graphs for all odd \(n\) between 5 and 17.
The results of our sampling, shown in Figures~\ref{figallWM}~and~\ref{figWM13}, support Conjecture~\ref{conjwindmill} for these values of \(n\).

\begin{figure}
    \begin{center}
      \includegraphics[width=10cm]{vert_facet_plot.eps}
      \end{center}
    \caption{For each odd \(n\) between 5 and 17, the plot shows the log of the number of facets of \(\PG\) for samples of graphs \(G\) with \(n\) vertices and \(3(n-1)/2\) edges with a target sample size of 200 graphs for each \(n\). The line is \( y=\frac{\log(6)}{2}(x-1)\), indicating \(\facets(\windmill(n))\) for each \(n\).}
    \label{figallWM}
\end{figure}

\begin{figure}
    \begin{center}
      \includegraphics[width=10cm]{13_histogram.eps}
      \end{center}
    \caption{For \(n=13\), the histogram shows the distribution of \(\facets(\PG)\) for our sample graphs. Not only does the maximum number of facets in our sample occur at \(6^6=\facets(\windmill(13))\), but there is a significant gap between our maximizer and all other facet counts in our sample.}
    \label{figWM13}
\end{figure}

The complexity of counting facets and determining which graphs are facet-maximizers in a case as small as graphs with \(n\) vertices and \(n+1\) edges was unexpected and indicates that there are many factors at play.
Therefore, counting the facets of symmetric edge polytopes remains an interesting problem in terms of both establishing formulas and investigating new techniques.

\section{Acknowledgments}

Both authors were partially supported by National Science Foundation award DMS-1953785.
The authors thank Rob Davis and Tianran Chen for helpful discussions.
The authors thank the anonymous referees for many helpful suggestions and references.
The authors made extensive use of both OEIS~\cite{oeis} and SageMath~\cite{sage} in this work.

\begin{thebibliography}{10}

\bibitem{chen2021facets}
T. Chen, R. Davis, and E. Korchevskaia,
\newblock Facets and facet subgraphs of symmetric edge polytopes,
\newblock {\em Discrete Appl. Math.} \textbf{328} (2023), 139--153.

\bibitem{chen2017counting}
T. Chen, R. Davis, and D. Mehta,
\newblock Counting equilibria of the {K}uramoto model using birationally
  invariant intersection index,
\newblock {\em SIAM J. Appl. Algebra Geom.} \textbf{2} (2018), 489--507.

\bibitem{chen2020graphadjacency}
T. Chen and E. Korchevskaia,
\newblock Graph edge contraction and subdivisions for adjacency polytopes, arxiv preprint arXiv:1912.02841 [math.CO],
  2020. Available at \url{https://arxiv.org/abs/1912.02841}.

\bibitem{dali2022gammavector}
A. D'Al\'i, M. Juhnke-Kubitzke, D. K\"ohne, and L. Venturello,
\newblock On the gamma-vector of symmetric edge polytopes,
\newblock {\em SIAM J. Discrete Math.} \textbf{37} (2023), 487--515.

\bibitem{dalidelucchimichalek}
A. D'Al\'i, E. Delucchi, and M. Micha\l ek,
\newblock Many faces of symmetric edge polytopes,
\newblock {\em Electron. J. Combin.} \textbf{29} (2022), Paper No.\ 3.24.

\bibitem{thetagraphs}
R.~J. Faudree and M.~Simonovits,
\newblock On a class of degenerate extremal graph problems,
\newblock {\em Combinatorica} \textbf{3} (1983), 83--93.

\bibitem{SIAMMCMC}
B. Fosdick, D. Larremore, J. Nishimura, and J. Ugander,
\newblock Configuring random graph models with fixed degree sequences,
\newblock {\em SIAM Rev.} \textbf{60} (2018), 315--355.

\bibitem{HenkRichterZiegler}
M. Henk, J. Richter-Gebert, and G. Ziegler,
\newblock Basic properties of convex polytopes,
\newblock in {\em Handbook of Discrete and Computational Geometry}, CRC Press
  Ser. Discrete Math. Appl., 1997, pp.\ 243--270.

\bibitem{higashitanifanopolytopes}
A. Higashitani,
\newblock Smooth fano polytopes arising from finite directed graphs,
\newblock {\em Kyoto J. Math.} \textbf{55} (2015), 579--592.

\bibitem{higashitanijochemkomateusz}
A. Higashitani, K. Jochemko, and M. Micha\l ek,
\newblock Arithmetic aspects of symmetric edge polytopes,
\newblock {\em Mathematika} \textbf{65} (2019), 763--784.

\bibitem{kalman2022ehrhart}
T. K\'alm\'an and L. T\'othm\'er\'esz,
\newblock Ehrhart theory of symmetric edge polytopes via ribbon structures, arxiv preprint arXiv:2201.10501 [math.CO], 2022. Available at \url{https://arxiv.org/abs/2201.10501}.

\bibitem{matsuietal2011}
T. Matsui, A. Higashitani, Y. Nagazawa, H. Ohsugi, and
  T. Hibi,
\newblock Roots of {E}hrhart polynomials arising from graphs,
\newblock {\em J. Algebraic Combin.} \textbf{34} (2011), 721--749.

\bibitem{NillClassification}
B. Nill,
\newblock Classification of pseudo-symmetric simplicial reflexive polytopes,
\newblock in {\em Algebraic and Geometric Combinatorics},  
{\it Contemp. Math.}, Vol. 443, Amer. Math. Soc., 2006, pp.\ 269--282.

\bibitem{oeis}
OEIS~Foundation Inc.
\newblock The {O}n-{L}ine {E}ncyclopedia of {I}nteger {S}equences, 2023.
\newblock Published electronically at \url{https://oeis.org}.

\bibitem{smoothfanoehrhart2012}
H. Ohsugi and K. Shibata,
\newblock Smooth {F}ano polytopes whose {E}hrhart polynomial has a root with
  large real part,
\newblock {\em Discrete Comput. Geom.} \textbf{47} (2012), 624--628.

\bibitem{osughitsuchiya2020}
H. Ohsugi and A. Tsuchiya,
\newblock The $h^*$-polynomials of locally anti-blocking lattice polytopes and
  their $\gamma $-positivity,
\newblock {\em Discrete Comput. Geom.} \textbf{66} (2020), 701--722.

\bibitem{symmetricedgematchingpolys}
H. Ohsugi and A. Tsuchiya,
\newblock Symmetric edge polytopes and matching generating polynomials,
\newblock {\em Comb. Theory} \textbf{1} (2021), Paper No.\ 9.

\bibitem{robbins1955stirling}
H. Robbins,
\newblock A remark on {S}tirling's formula,
\newblock {\em Amer. Math. Monthly} \textbf{62} (1955), 26--29.

\bibitem{sage}
{The Sage Developers}.
\newblock {\em {S}ageMath, the {S}age {M}athematics {S}oftware {S}ystem
  ({V}ersion 9.2)}, 2020.
\newblock Available at \url{https://www.sagemath.org}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 \textit{Mathematics Subject Classification}:  Primary 52B20;  Secondary 52B05, 52B12.

\noindent {\textit{Keywords}:} symmetric edge polytope, facet, binomial coefficient.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A027383},
\seqnum{A360408}, and
\seqnum{A360409}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 28 2023; 
revised versions received  July 7 2023; July 11 2023.
Published in {\it Journal of Integer Sequences}, July 24 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>