$\lVert R_{i}\hat{u}_{i}\rVert=\sqrt{1-\hat{c}_{i}^{2}}\lVert
R_{i}\hat{u}_{\perp,i}\rVert\geq\sqrt{1-\hat{c}_{i}^{2}}\sigma_{iJ}\geq\sqrt{1-\hat{c}_{i}^{2}}\frac{\epsilon}{2},$

and thus

$1-\hat{c}_{i}^{2}\leq\frac{4}{\epsilon^{2}}\lVert\hat{R}_{i}-R_{i}\rVert_{F}^{2}\iff|\hat{c}_{i}|\geq\sqrt{1-\frac{4}{\epsilon^{2}}\lVert\hat{R}_{i}-R_{i}\rVert_{F}^{2}}.$

Hence,

$|\hat{u}_{i}^{\prime}1|\geq\sqrt{1-\frac{4}{\epsilon^{2}}\lVert\hat{R}_{i}-R_{i}\rVert_{F}^{2}}-\frac{2\sqrt{J+1}}{\epsilon}\lVert\hat{R}_{i}-R_{i}\rVert_{F}.$

Suppose $\lVert R_{i}-\hat{R}_{i}\rVert_{F}<\epsilon/(4\sqrt{J+1})$, then

$|\hat{u}_{i}^{\prime}1|\geq\sqrt{1-\frac{1}{J+1}}-\frac{1}{2}\geq\sqrt{1/2}-1/2\geq
0.207.$

Thus, if we pick $C$ so that $1/C<0.207$, then

$E_{i}\subset\left\\{{\hat{\sigma}_{iJ}<\epsilon/4}\right\\}\cup\left\\{{\hat{\sigma}_{iJ}>\epsilon/4,|\hat{u}_{i}^{\prime}1|<1/C}\right\\}\subset\left\\{{\lVert
R_{i}-\hat{R}_{i}\rVert_{F}>\frac{\epsilon}{4\sqrt{J+1}}}\right\\}.$

As a result,

$\operatorname{P}\left[{\bigcup_{i}E_{i}}\right]\leq\operatorname{P}\left[{\max_{i\in[n]}\lVert
R_{i}-\hat{R}_{i}\rVert_{F}>\frac{\epsilon}{4\sqrt{J+1}}}\right]\to 0$

by assumption. This proves the first part regarding the existence of a unique
bounded implicit design.

For the second part, note that when $\hat{\sigma}_{iJ}>0$,

$\hat{\pi}_{i}-\pi_{i}=\frac{\hat{u}_{i}}{1^{\prime}\hat{u}_{i}}-\frac{u_{i}}{1^{\prime}u_{i}}=\frac{1^{\prime}}{1^{\prime}\hat{u}_{i}}(u_{i}-\hat{u}_{i})\frac{\hat{u}_{i}}{1^{\prime}u_{i}}+\frac{1}{1^{\prime}u_{i}}(\hat{u}_{i}-u_{i}).$

Thus

$\lVert\hat{\pi}_{i}-\pi_{i}\rVert_{2}\leq\frac{1}{0.207}\sqrt{J+1}\lVert
u_{i}-\hat{u}_{i}\rVert_{2}+\lVert\hat{u}_{i}-u_{i}\rVert_{2}$

if $\lVert R_{i}-\hat{R}_{i}\rVert_{F}\leq\epsilon/(4\sqrt{J+1})$.

Now,

$\displaystyle\lVert\hat{u}_{i}-u_{i}\rVert_{2}$
$\displaystyle\leq(1-\hat{c}_{i})+\sqrt{1-\hat{c}_{i}^{2}}\leq\sqrt{1-\hat{c}_{i}^{2}}\frac{\sqrt{1-\hat{c}_{i}}+\sqrt{1+\hat{c}_{i}}}{\sqrt{1+\hat{c}_{i}}}\leq\sqrt{1-\hat{c}_{i}^{2}}(1+\sqrt{2})$
$\displaystyle\leq\frac{2(1+\sqrt{2})}{\epsilon}\lVert
R_{i}-\hat{R}_{i}\rVert_{F}$

Therefore,

$\lVert\hat{\pi}_{i}-\pi_{i}\rVert_{2}\leq\underbrace{\left({\frac{1}{0.207}(\sqrt{J+1}+1)\frac{2(1+\sqrt{2})}{\epsilon}}\right)}_{M/\epsilon}\lVert
R_{i}-\hat{R}_{i}\rVert_{F}.$

Hence, for $\eta>0$,

$\left\\{{\max_{i\in[n]}\lVert\hat{\pi}_{i}-\pi_{i}\rVert_{2}>\eta}\right\\}\subset\left\\{{\max_{i\in[n]}\lVert
R_{i}-\hat{R}_{i}\rVert_{F}>\max\left({\frac{\epsilon}{4\sqrt{J+1}},\frac{\eta\epsilon}{M}}\right)}\right\\}$

The probability on the right-hand side converges to zero by assumption. This
proves the convergence of $\hat{\pi}_{i}$ to $\pi_{i}$ uniformly in $i$ in
$\lVert\cdot\rVert_{2}$. Since
$\lVert\cdot\rVert_{\infty}\leq\lVert\cdot\rVert_{2}$ in $\mathbb{R}^{J+1}$,
this concludes the proof. ∎

See 4.1

###### Proof.

By Theorem B.1, the potential weights for this regression specification are
the same as the regression specification with the covariate
$W_{i}-x_{i}^{\prime}\beta_{w\to x}$, where $\beta_{w\to x}$ is the population
projection of $W_{i}$ (and hence $\pi_{i}^{*}$) on $x_{i}$. Thus the potential
weights are

$\rho_{i}(w)=V^{-1}\left[{w-x_{i}^{\prime}\beta_{w\to x}}\right].$

where $V>0$ by Theorem B.1. Note that since $V>0$,
$\rho_{i}(1)\neq\rho_{i}(0)$ for all $i$, and thus the implicit design is
unique and equal to $\pi_{i}=x_{i}^{\prime}\beta_{w\to x}.$ The corresponding
implicit weight $\omega_{i}$ is then $V^{-1}\pi_{i}(1-\pi_{i})$.

Lastly, we verify that $V=\frac{1}{n}\sum_{i=1}^{n}\pi_{i}(1-\pi_{i})$:

$\displaystyle
0<V=\frac{1}{n}\sum_{i}\pi_{i}(1-\pi_{i})^{2}+(1-\pi_{i})\pi_{i}^{2}=\frac{1}{n}\sum_{i}\pi_{i}(1-\pi_{i}).$

Note that $\omega_{i}=\pi_{i}(1-\pi_{i})/V$ is negative if and only if
$\pi_{i}\not\in[0,1]$. ∎

See 4.2

###### Proof.

By Theorem B.1, the potential weights for this regression specification are
equivalent to the potential weights in the specification

$Y_{i}=\tau(W_{i}-\tilde{\pi}_{i}-\Gamma_{2}^{\prime}(W_{i}(x_{i}-\overline{x})-\Gamma_{0}-\Gamma_{1}(x_{i}-\overline{x})))+\epsilon_{i}.$

We can then readily compute that

$\rho_{i}(0)=V^{-1}(-\tilde{\pi}-\Gamma_{2}^{\prime}(-\Gamma_{0}-\Gamma_{1}(x_{i}-\overline{x})))\quad\rho_{i}(1)=V^{-1}(1-\tilde{\pi}-\Gamma_{2}^{\prime}(x_{i}-\overline{x}-\Gamma_{0}-\Gamma_{1}(x_{i}-\overline{x}))).$

where $V>0$ by Theorem B.1.

Thus, all implicit designs must satisfy

$\pi_{i}=\frac{-\rho_{i}(0)}{\rho_{i}(1)-\rho_{i}(0)}=\frac{\tilde{\pi}_{i}-\Gamma_{2}^{\prime}(\Gamma_{0}+\Gamma_{1}(x_{i}-\overline{x}))}{1-\Gamma_{2}^{\prime}(x_{i}-\overline{x})}$

for those with $1-\Gamma_{2}^{\prime}(x_{i}-\overline{x})\neq 0$.

For (i), $\tau$ is a causal contrast under $\bm{\pi}^{*}$ if and only if
$\bm{\pi}^{*}$ belongs to the set of implicit designs. This is further
equivalent to (4.1.2). When $\pi_{i}^{*}(x_{i}-\overline{x})$ is affine, then
the right-hand side of (4.1.2) is zero, and thus (4.1.2) is equivalent to
$\bm{\pi}^{*}=\tilde{\bm{\pi}}$, meaning that $\bm{\pi}^{*}$ is affine in
$x_{i}$. When this happens,

$\pi_{i}=\frac{\pi_{i}^{*}-\pi_{i}^{*}\Gamma_{2}^{\prime}(x_{i}-\overline{x})}{1-\Gamma_{2}^{\prime}(x_{i}-\overline{x})}=\pi_{i}^{*}$

when $1-\Gamma_{2}^{\prime}(x_{i}-\overline{x})\neq 0$. Computing the implicit
weight in this case yields

$\displaystyle\omega_{i}$ $\displaystyle=\pi_{i}^{*}\rho_{i}(1)$
$\displaystyle=V^{-1}\left[{\pi_{i}^{*}(1-\pi_{i}^{*})-\Gamma_{2}^{\prime}(\pi_{i}^{*}(x_{i}-\overline{x})-\pi_{i}^{*}\Gamma_{0}-\pi_{i}^{*}\Gamma_{1}(x_{i}-\overline{x}))}\right]$
$\displaystyle=V^{-1}\left[{\pi_{i}^{*}(1-\pi_{i}^{*})-\Gamma_{2}^{\prime}(1-\pi_{i}^{*})(\Gamma_{0}+\Gamma_{1}(x_{i}-\overline{x}))}\right]$
($\pi_{i}^{*}(x_{i}-\overline{x})=\Gamma_{0}+\Gamma_{1}(x_{i}-\overline{x})$)
$\displaystyle=V^{-1}\pi_{i}^{*}(1-\pi_{i}^{*})(1-\Gamma_{2}^{\prime}(x_{i}-\overline{x})).$
($\pi_{i}^{*}(x_{i}-\overline{x})=\Gamma_{0}+\Gamma_{1}(x_{i}-\overline{x})$)

Hence, $\omega_{i}$ is proportional to
$\pi_{i}^{*}(1-\pi_{i}^{*})(1-\Gamma_{2}^{\prime}(x_{i}-\overline{x}))$.

For (ii), $\tau$ is a causal contrast if and only if (4.1.2) holds. Since
$\pi_{i}^{*}$ is assumed to be affine, the left-hand side of (4.1.2) is zero.
Since $\pi_{i}^{*}(x_{i}-\overline{x})$ is generically non-affine, the right-
hand side is zero for every $i$ if and only if $\Gamma_{2}=0$. By the
definition of $\Gamma_{2}$ as a projection coefficient, it is zero if and only
if

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{W_{i}}\left[{(W_{i}-\tilde{\pi}_{i})\cdot\left({W_{i}(x_{i}-\overline{x})-\Gamma_{0}-\Gamma_{1}(x_{i}-\overline{x})}\right)}\right]=0.$

This condition is further equivalent to

$\frac{1}{n}\sum_{i=1}^{n}\pi_{i}^{*}(1-\pi_{i}^{*})(x_{i}-\overline{x})=0.$

When this happens, since $\Gamma_{2}=0$, the implicit weight is proportional
to $\pi_{i}^{*}(1-\pi_{i}^{*})$. ∎

See 4.3

###### Proof.

  1. (i)

By Theorem B.1, it suffices to compute potential weights for the two-way
residualized specification. That is, let

$\mathbf{z}_{i}(\mathbf{w})=\begin{bmatrix}f_{1}(\mathbf{w})^{\prime}\\\
\vdots\\\ f_{T}(\mathbf{w})^{\prime}\end{bmatrix}\equiv\mathbf{z}(\mathbf{w})$

be the covariate transform. Note that the population residual of projecting
$\mathbf{z}_{i}(\mathbf{W}_{i})$ on unit and time fixed effect is

$\displaystyle\ddot{\mathbf{z}}(\mathbf{w})$
$\displaystyle=\mathbf{z}(\mathbf{w})-1_{T}\frac{1_{T}^{\prime}}{T}\mathbf{z}(\mathbf{w})-\frac{1}{n}\sum_{i=1}^{n}\sum_{\mathbf{w}^{\prime}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w}^{\prime})\mathbf{z}(\mathbf{w}^{\prime})+1_{T}\frac{1_{T}^{\prime}}{T}\frac{1}{n}\sum_{i=1}^{n}\sum_{\mathbf{w}^{\prime}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w}^{\prime})\mathbf{z}(\mathbf{w}^{\prime})$
$\displaystyle=\mathbf{z}(\mathbf{w})-1_{T}\frac{1_{T}^{\prime}}{T}\mathbf{z}(\mathbf{w})-\sum_{\mathbf{w}^{\prime}\in\mathcal{W}}\pi(\mathbf{w})\mathbf{z}(\mathbf{w}^{\prime})+1_{T}\frac{1_{T}^{\prime}}{T}\sum_{\mathbf{w}^{\prime}\in\mathcal{W}}\pi(\mathbf{w}^{\prime})\mathbf{z}(\mathbf{w}^{\prime})$

Thus the potential weights are

$\bm{\rho}_{i}(\mathbf{w})=\Lambda\left({\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\ddot{\mathbf{z}}(\mathbf{w})^{\prime}\ddot{\mathbf{z}}(\mathbf{w})]}\right)^{-1}\ddot{\mathbf{z}}(\mathbf{w})^{\prime}$

Note that

$\sum_{\mathbf{w}\in\mathcal{W}}\pi(\mathbf{w})\bm{\rho}_{i}(\mathbf{w})=\Lambda\left({\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\ddot{\mathbf{z}}(\mathbf{w})^{\prime}\ddot{\mathbf{z}}(\mathbf{w})]}\right)^{-1}\underbrace{\left({\sum_{\mathbf{w}\in\mathcal{W}}\pi(\mathbf{w})\ddot{\mathbf{z}}(\mathbf{w})^{\prime}}\right)}_{=0}=0.$

Therefore $\bm{\pi}$ defined by $\pi_{i}(\mathbf{w})=\pi(\mathbf{w})$ is a
valid implicit design. It is proper by definition. Now, let
$\dot{\mathbf{z}}(\mathbf{w})$ be the within-transformed covariate transform
for this regression (which includes the time fixed effects), which does not
depend on $i$. Note that the Gram matrix is

$G_{n}(\bm{\pi}^{*})=\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[\dot{\mathbf{z}}(\mathbf{w})^{\prime}\dot{\mathbf{z}}(\mathbf{w})]=\sum_{\mathbf{w}\in\mathcal{W}}\pi(\mathbf{w})\dot{\mathbf{z}}(\mathbf{w})^{\prime}\dot{\mathbf{z}}(\mathbf{w})=G_{n}(\bm{\pi}).$

Thus $\bm{\pi}$ is Gram-consistent.

The argument for the estimated implicit design is analogous. The sample
residuals of $\mathbf{z}(\mathbf{W}_{i})$ regressing on unit and time fixed
effects is

$\mathbf{z}(\mathbf{W}_{i})-1_{T}\frac{1_{T}^{\prime}}{T}\mathbf{z}(\mathbf{W}_{i})-\sum_{\mathbf{w}^{\prime}\in\mathcal{W}}\hat{\pi}(\mathbf{w}^{\prime})\mathbf{z}(\mathbf{w}^{\prime})+\sum_{\mathbf{w}^{\prime}\in\mathcal{W}}\hat{\pi}(\mathbf{w}^{\prime})1_{T}\frac{1_{T}^{\prime}}{T}\mathbf{z}(\mathbf{w}^{\prime})$

where
$\hat{\pi}(\mathbf{w})=\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}(\mathbf{W}_{i}=\mathbf{w})$.
The estimated potential weights are proportional to these residuals evaluated
at $\mathbf{W}_{i}=\mathbf{w}$. Thus $\hat{\bm{\pi}}$ defined by
$\hat{\pi}_{i}(\cdot)=\hat{\pi}(\cdot)$ solves (3.3).

  2. (ii)

In this case, the population residuals are

$\displaystyle\ddot{\mathbf{z}}(\mathbf{w})$
$\displaystyle=\mathbf{w}-1_{T}\frac{1_{T}^{\prime}}{T}\mathbf{w}-\sum_{\mathbf{w}_{1}\in\mathcal{W}}\pi(\mathbf{w}_{1})\mathbf{w}_{1}+1_{T}\frac{1_{T}^{\prime}}{T}\sum_{\mathbf{w}_{1}\in\mathcal{W}}\pi(\mathbf{w}_{1})\mathbf{w}_{1}.$

Any implicit design $\tilde{\pi}_{i}$ satisfies

$\sum_{\mathbf{w}\in\mathcal{W}}\tilde{\pi}_{i}(\mathbf{w})\mathbf{w}-1_{T}\sum_{\mathbf{w}\in\mathcal{W}}\tilde{\pi}_{i}(\mathbf{w})\frac{1_{T}^{\prime}\mathbf{w}}{T}-\sum_{\mathbf{w}\in\mathcal{W}}\pi(\mathbf{w})\mathbf{w}+1_{T}\sum_{\mathbf{w}\in\mathcal{W}}\pi(\mathbf{w})\frac{1_{T}^{\prime}}{T}\mathbf{w}=0$

This implies that the vector

$\sum_{\mathbf{w}\in\mathcal{W}}\left({\tilde{\pi}_{i}(\mathbf{w})-\pi(\mathbf{w})}\right)\mathbf{w}\in\operatorname{span}(1_{T})$

However, the only vector in $\operatorname{span}(1_{T})$ and
$\operatorname{span}(\mathcal{W})$ is the zero vector by assumption. Thus
$\sum_{\mathbf{w}\in\mathcal{W}}\left({\tilde{\pi}_{i}(\mathbf{w})-\pi(\mathbf{w})}\right)\mathbf{w}=\sum_{\mathbf{w}\in\mathcal{W},\mathbf{w}\neq
0}\left({\tilde{\pi}_{i}(\mathbf{w})-\pi(\mathbf{w})}\right)\mathbf{w}=0$.
Since $\mathcal{W}\setminus\left\\{{0}\right\\}$ is a linearly independent
collection of vectors, we conclude that
$\tilde{\pi}_{i}(\mathbf{w})=\pi(\mathbf{w})$ for all $\mathbf{w}\neq 0$.
Since both probability vectors sum to one, we conclude that
$\tilde{\pi}_{i}(\mathbf{w})=\pi(\mathbf{w})$. Therefore, $\pi(\mathbf{w})$ in
((i)) is the unique implicit design. The proof for the uniqueness of the
estimated implicit design is analogous. ∎

See 4.4

###### Proof.

By Theorem B.1, we can focus on the population regression of $\mathbf{y}_{i}$
on $\ddot{\mathbf{W}}_{i}-\ddot{\mathbf{x}}_{i}\beta_{w\to x}$. The potential
weight vector is then

$\bm{\rho}_{i}(\mathbf{w})=\frac{\ddot{\mathbf{w}}-\ddot{\mathbf{x}}_{i}\beta_{w\to
x}}{\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{\mathbf{W}_{i}\sim\pi_{i}^{*}(\cdot)}\left[{(\ddot{\mathbf{W}}_{i}-\ddot{\mathbf{x}}_{i}\beta_{w\to
x})^{\prime}(\ddot{\mathbf{W}}_{i}-\ddot{\mathbf{x}}_{i}\beta_{w\to
x})}\right]}.$

where the denominator is strictly positive by Theorem B.1. Here, the notation
$\ddot{\mathbf{z}}_{i}$ for $T\times m$ matrices
$\mathbf{z}_{1}(\mathbf{w}),\ldots,\mathbf{z}_{n}(\mathbf{w})$ is defined as
the population residual against unit and time fixed effects:

$\ddot{\mathbf{z}}_{i}=\mathbf{z}_{i}-1_{T}\frac{1_{T}^{\prime}\mathbf{z}_{i}}{T}-\frac{1}{n}\sum_{j=1}^{n}\sum_{\mathbf{w}}\mathbf{z}_{j}(\mathbf{w})\pi_{j}^{*}(\mathbf{w})+1_{T}\frac{1_{T}^{\prime}}{T}\frac{1}{n}\sum_{j=1}^{n}\sum_{\mathbf{w}}\mathbf{z}_{j}(\mathbf{w})\pi_{j}^{*}(\mathbf{w}).$

The condition (2.2) is then

$\displaystyle 0$
$\displaystyle=\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}(\mathbf{w})\rho_{i}(\mathbf{w})$
$\displaystyle\implies\ddot{\mathbf{x}}_{i}\beta_{w\to x}$
$\displaystyle=\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}(\mathbf{w})\ddot{\mathbf{w}}$

The right-hand side is a linear combination of the columns of $\mathcal{W}$
and $1_{T}$. Thus, a necessary condition for the existence of implicit designs
is that $\ddot{\mathbf{x}}_{i}\beta_{w\to
x}\in\operatorname{span}(\mathcal{W}\cup\left\\{{1_{T}}\right\\}).$ The left-
hand side is further more

$\left({\mathbf{x}_{i}-\frac{1}{n}\sum_{j=1}^{n}\mathbf{x}_{j}}\right)\beta_{w\to
x}+c1_{T}$

for some scalar $c$. Thus, a necessary condition is furthermore

$\left({\mathbf{x}_{i}-\frac{1}{n}\sum_{j=1}^{n}\mathbf{x}_{j}}\right)\beta_{w\to
x}\in\operatorname{span}(\mathcal{W}\cup\left\\{{1_{T}}\right\\}).\qed$

See 4.5

###### Proof.

For a given unit $i$ and $t\in\mathcal{T}_{i}$, let $L_{i}=|\mathcal{T}_{i}|$
and let $R_{i}(\mathbf{w})=\sum_{s\in\mathcal{T}_{i}}\mathbf{w}_{s}$. The
covariate transform—where we specify the unit fixed effect via within
transformation—is

$z_{it}(\mathbf{w})^{\prime}=[\dot{\mathbbm{1}}_{it1},\ldots,\dot{\mathbbm{1}}_{itT},\dot{\mathbf{w}}_{t}]$

where

$\dot{\mathbbm{1}}_{its}=\begin{cases}0&s\not\in\mathcal{T}_{i}\\\
1-\frac{1}{L_{i}}&s=t\\\
-\frac{1}{L_{i}}&s\in\mathcal{T}_{i}\setminus\left\\{{t}\right\\}\end{cases}$

is the demeaned time dummy and

$\dot{\mathbf{w}}_{t}=\mathbf{w}_{t}-Q_{i}(\mathbf{w}).$

By Theorem B.1, it suffices to analyze the potential weights of regressing
$Y_{it}$ on $\ddot{W}_{it}$, where

$\ddot{W}_{it}=\dot{W_{it}}-\sum_{s=1}^{T}\delta_{s}\dot{\mathbbm{1}}_{its}=\dot{W_{it}}-\sum_{s\in\mathcal{T}_{i}}\delta_{s}\dot{\mathbbm{1}}_{its}.$

and $\delta_{s}$ are the population projection coefficients of $\dot{W}_{it}$
on $\dot{\mathbbm{1}}_{its}$. Let
$V\equiv\frac{1}{n}\sum_{i=1}^{n}\sum_{t\in\mathcal{T}_{i}}\mathbb{E}[\ddot{W}_{it}^{2}]$,
which is strictly positive by Theorem B.1. The potential weights are then

$\bm{\rho}_{it}(\mathbf{w})=V^{-1}\left({\dot{\mathbf{w}}_{t}-\sum_{s\in\mathcal{T}_{i}}\delta_{s}\dot{\mathbbm{1}}_{its}}\right)=V^{-1}\left({\dot{\mathbf{w}}_{t}-\delta_{t}+\frac{1}{L_{i}}\sum_{s\in\mathcal{T}_{i}}\delta_{s}}\right).$

An implicit design $\bm{\pi}$ exists if and only if there is some
$\pi_{i}(\cdot)$ and $\sum_{\mathbf{w}}\pi_{i}(\mathbf{w})=1$ such that

$\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}(\mathbf{w})\bm{\rho}_{it}(\mathbf{w})=0\text{
for all $i$ and $t\in\mathcal{T}_{i}$}.$

This is further equivalent to that for all $i$, $t\in\mathcal{T}_{i}$,

$\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}(\mathbf{w})\left({\mathbf{w}_{t}-\frac{R_{i}(\mathbf{w})}{L_{i}}}\right)=\delta_{t}-\frac{1}{L_{i}}\sum_{s\in\mathcal{T}_{i}}\delta_{s}.$

Suppose first that such a $\bm{\pi}$ exists. Fix $t\in\mathcal{T}$ and
consider two units $i,j$, where
$\mathcal{T}_{i}\cap\mathcal{T}_{j}\supset\mathcal{T}$ by assumption. Then, by
(A), we have that

$\delta_{t}=\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}(\mathbf{w})\mathbf{w}_{t}-\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}(\mathbf{w})\frac{R_{i}}{L_{i}}+\frac{1}{L_{i}}\sum_{s\in\mathcal{T}_{i}}\delta_{s}=\sum_{\mathbf{w}\in\mathcal{W}}\pi_{j}(\mathbf{w})\mathbf{w}_{t}-\sum_{\mathbf{w}\in\mathcal{W}}\pi_{j}(\mathbf{w})\frac{R_{j}}{L_{j}}+\frac{1}{L_{j}}\sum_{s\in\mathcal{T}_{j}}\delta_{s}.$

Thus, rearranging, we have for all $t\in\mathcal{T}$,

$\sum_{\mathbf{w}\in\mathcal{W},\mathbf{w}\neq
0}(\pi_{i}(\mathbf{w})-\pi_{j}(\mathbf{w}))\mathbf{w}_{t}=M(i,j)$

where $M(i,j)$ does not depend on $t$. Viewed as linear combinations for
vectors in $\mathcal{W}_{\mathcal{T}}$, the left-hand side collecting over all
$t\in\mathcal{T}$ lies in the span of $\mathcal{W}_{\mathcal{T}}$. The right-
hand side lies in the span of the constant vector on $|\mathcal{T}|$
dimensions. By assumption, these two spans contain only the zero vector in
common. Thus, both sides are equal to zero:

$\sum_{\mathbf{w}\in\mathcal{W},\mathbf{w}\neq
0}(\pi_{i}(\mathbf{w})-\pi_{j}(\mathbf{w}))\mathbf{w}_{t}=0\text{ for all
$t\in\mathcal{T}$}.$

By linear independence of vectors in $\mathcal{W}_{\mathcal{T}}$, we conclude
that $\pi_{i}(\mathbf{w})=\pi_{j}(\mathbf{w})$. Therefore, the implicit design
must be constant across units:

$\pi_{i}(\mathbf{w})=\pi(\mathbf{w})$

for some $\pi(\cdot)$.

Next, we show that if $\bm{\pi}$ exists, then it must equal to
$\overline{\pi}(\cdot)$. The fact that $\delta_{t}$ are projection
coefficients is equivalent to the following orthogonality conditions holding
for all $t\in[T]$: For all $s\in\left\\{{1,\ldots,T}\right\\}$,

$\displaystyle 0$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\sum_{t\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\ddot{\mathbf{w}}_{it}\dot{\mathbbm{1}}_{its}$
$\displaystyle=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\sum_{t\in\mathcal{T}_{i}}\left({\mathbf{w}_{t}-R_{i}(\mathbf{w})/L_{i}-\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}\dot{\mathbbm{1}}_{it\ell}}\right)\dot{\mathbbm{1}}_{its}$
$\displaystyle=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\sum_{t\in\mathcal{T}_{i}}\left({\mathbf{w}_{t}-R_{i}(\mathbf{w})/L_{i}}\right)\dot{\mathbbm{1}}_{its}-\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{t\in\mathcal{T}_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}\dot{\mathbbm{1}}_{it\ell}\dot{\mathbbm{1}}_{its}$
$\displaystyle=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\sum_{t\in\mathcal{T}_{i}}\left({\mathbf{w}_{t}-R_{i}(\mathbf{w})/L_{i}}\right)\mathbbm{1}(t=s)-\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{t\in\mathcal{T}_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}\mathbbm{1}(t=\ell)\dot{\mathbbm{1}}_{its}$
($\dot{\mathbf{w}}$ and $\dot{\mathbbm{1}}_{i}$ sum to zero over
$t\in\mathcal{T}_{i}$)
$\displaystyle=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\left({\mathbf{w}_{s}-R_{i}(\mathbf{w})/L_{i}}\right)-\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}\dot{\mathbbm{1}}_{i\ell
s}$
$\displaystyle=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\left({\mathbf{w}_{s}-R_{i}(\mathbf{w})/L_{i}}\right)-\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}(\mathbbm{1}(\ell=s)-1/L_{i})$

Rearranging, we have that the orthogonality condition is equivalent to

$\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\left({\mathbf{w}_{s}-Q_{i}(\mathbf{w})}\right)=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\left({\delta_{s}-\frac{1}{L_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}}\right)$

for all $s\in[T]$.

Pick $t\in\mathcal{T}$ and consider the corresponding (A). Note that
$t\in\mathcal{T}_{i}$ for all $i$, and hence

$\delta_{t}=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{L_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}+\sum_{\mathbf{w}\in\mathcal{W}}\underbrace{\left({\frac{1}{n}\sum_{i=1}^{n}\pi_{i}^{*}(\mathbf{w})}\right)}_{\overline{\pi}(\mathbf{w})}\mathbf{w}_{t}-\frac{1}{n}\sum_{i=1}^{n}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})Q_{i}(\mathbf{w}).$

Therefore, again, given (A) and $\pi_{i}(\mathbf{w})=\pi(\mathbf{w})$,

$\sum_{\mathbf{w}\in\mathcal{W},\mathbf{w}\neq
0}(\pi(\mathbf{w})-\overline{\pi}(\mathbf{w}))\mathbf{w}_{t}=M^{\prime}(i)$

for some $M^{\prime}(i)$ that does not depend $t\in\mathcal{T}$. By the same
argument as above, we have that

$\pi(\mathbf{w})=\overline{\pi}(\mathbf{w})\text{ for all $\mathbf{w}\neq
0$}\implies\pi(\mathbf{w})=\overline{\pi}(\mathbf{w})\text{ for all
$\mathbf{w}\in\mathcal{W}$}.$

Now, we plug $\pi_{i}(\mathbf{w})=\overline{\pi}(\mathbf{w})$ into (A), and
then plug the expression into (A). We obtain that for all $t\in[T]$,

$\sum_{i:t\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})(\mathbf{w}_{t}-Q_{i}(\mathbf{w}))=\sum_{i:t\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\overline{\pi}(\mathbf{w})(\mathbf{w}_{t}-Q_{i}(\mathbf{w})).$

This is (4.5). Thus, we proved that if an implicit design exists, then the
above condition holds and it must be uniquely equal to
$\overline{\pi}(\cdot)$.

For the reverse direction, let us assume that (4.5) holds. For a given $t$,
set

$\delta_{t}=\sum_{\mathbf{w}\in\mathcal{W}}\overline{\pi}(\mathbf{w})\mathbf{w}_{t},$

and thus

$\delta_{t}-\frac{1}{L_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}=\sum_{\mathbf{w}\in\mathcal{W}}\overline{\pi}(\mathbf{w})\left({\mathbf{w}_{t}-Q_{i}(\mathbf{w})}\right).$

This means that $\pi_{i}(\mathbf{w})=\overline{\pi}(\mathbf{w})$ satisfies
(A). Thus $\overline{\pi}(\cdot)$ is an implicit design if (A) defines the
projection coefficients.

Summing over $i$ where $t\in\mathcal{T}_{i}$:

$\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\left\\{{\delta_{s}-\frac{1}{L_{i}}\sum_{\ell\in\mathcal{T}_{i}}\delta_{\ell}}\right\\}=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\overline{\pi}(\mathbf{w})\left({\mathbf{w}_{t}-Q_{i}(\mathbf{w})}\right)=\frac{1}{n}\sum_{i:s\in\mathcal{T}_{i}}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})(\mathbf{w}_{t}-Q_{i}(\mathbf{w})),$

where the last equality follows from (4.5). This verifies the orthogonality
condition (A) for $t$. Therefore, our choice of (A) does indeed equal the
projection coefficients. This concludes the proof. ∎

##  Appendix B Additional results

###  B.1. Invariances

######  Theorem B.1 (Frisch–Waugh–Lovell, in population).

Consider a population regression specification in the sense of 2.1. Partition
$z_{t}(\mathbf{x}_{i},\mathbf{w})$ into $z_{t1}(\cdot)$ and $z_{t2}(\cdot)$.
Suppose $\Lambda=[\Lambda_{1},0]$ loads solely in entries in $z_{t1}$:
$\Lambda z_{t}=\Lambda_{1}z_{t1}$. Let

$\Gamma=\left({\frac{1}{n}\sum_{i,t}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})z_{t1}(\mathbf{x}_{i},\mathbf{w})z_{t2}(\mathbf{x}_{i},\mathbf{w})^{\prime}}\right)\left({\frac{1}{n}\sum_{i,t}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})z_{t2}(\mathbf{x}_{i},\mathbf{w})z_{t2}(\mathbf{x}_{i},\mathbf{w})^{\prime}}\right)^{-1}$

be the population projection matrix of $z_{t1}$ onto $z_{t2}$. Define
$\tilde{z}_{t}(\mathbf{x}_{i},\mathbf{w})=z_{t1}(\mathbf{x}_{i},\mathbf{w})-\Gamma
z_{t2}(\mathbf{x}_{i},\mathbf{w})$. Consider the regression specification
defined by $\Lambda_{1},\tilde{z}_{t}(\cdot),$ and

$\tilde{G}_{n}=\frac{1}{n}\sum_{i,t}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\tilde{z}_{t}(\mathbf{x}_{i},\mathbf{w})\tilde{z}_{t}(\mathbf{x}_{i},\mathbf{w})^{\prime}.$

Then:

  1. (i)

$\Gamma,\tilde{G}_{n}$ are functions of the original Gram matrix $G_{n}$.
Since $G_{n}$ is assumed to be invertible, $\Gamma$ is well-defined and
$\tilde{G}_{n}$ is positive definite.

  2. (ii)

The potential weights associated with the two population regression
specifications are the same.

###### Proof.

Note that we can partition

$G_{n}=\frac{1}{n}\sum_{i,t}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})z_{t}(\mathbf{x}_{i},\mathbf{w})z_{t}(\mathbf{x}_{i},\mathbf{w})^{\prime}=\begin{bmatrix}G_{11}&G_{12}\\\
G_{21}&G_{22}\end{bmatrix}$

conformably where $G_{11}$ is the Gram matrix associated with $z_{t1}$ and
$G_{22}$ is the Gram matrix associated with $z_{t2}$. Observe that
$\Gamma=G_{12}G_{22}^{-1}$ and that $\tilde{G}_{n}=G_{11}-\Gamma G_{21}$. This
proves (i).

Since $G_{n}$ is symmetric and positive definite by assumption, $G_{11}$ and
$G_{22}$ are invertible. By the block matrix inversion formula,

$G_{n}^{-1}=\begin{bmatrix}(G_{11}-G_{12}G_{22}^{-1}G_{21})^{-1}&-(G_{11}-G_{12}G_{22}^{-1}G_{21})^{-1}G_{12}G_{22}^{-1}\\\
-G_{22}^{-1}G_{21}(G_{11}-G_{12}G_{22}^{-1}G_{21})^{-1}&G_{22}^{-1}+G_{22}^{-1}G_{21}(G_{11}-G_{12}G_{22}^{-1}G_{21})^{-1}G_{12}G_{22}^{-1}\end{bmatrix}.$

Hence

$\Lambda G_{n}^{-1}=\left[{\Lambda_{1}(G_{11}-\Gamma
G_{21})^{-1}\quad-\Lambda_{1}(G_{11}-\Gamma G_{21})^{-1}\Gamma}\right]$

Now, the potential weights for the original regression specification are

$\displaystyle\bm{\rho}_{it}(\mathbf{w})$
$\displaystyle=\Lambda_{1}(G_{11}-\Gamma
G_{21})^{-1}z_{t1}(\mathbf{x}_{i},\mathbf{w})-\Lambda_{1}(G_{11}-\Gamma
G_{21})^{-1}\Gamma z_{t2}(\mathbf{x}_{i},\mathbf{w})$
$\displaystyle=\Lambda_{1}(G_{11}-\Gamma
G_{21})^{-1}\tilde{z}_{t}(\mathbf{x}_{i},\mathbf{w})$
$\displaystyle=\Lambda_{1}\tilde{G}_{n}^{-1}\tilde{z}_{t}(\mathbf{x}_{i},\mathbf{w}).$

This proves (ii). ∎

######  Theorem B.2 (Frisch–Waugh–Lovell, in sample).

Consider a population regression specification in the sense of 2.1. Partition
$z_{t}(\mathbf{x}_{i},\mathbf{w})$ into $z_{t1}(\cdot)$ and $z_{t2}(\cdot)$.
Suppose $\Lambda=[\Lambda_{1},0]$ loads solely in entries in $z_{t1}$:
$\Lambda z_{t}=\Lambda_{1}z_{t1}$. Suppose the sample Gram matrix is
invertible. Let

$\hat{\Gamma}=\left({\frac{1}{n}\sum_{i,t}z_{t1}(\mathbf{x}_{i},\mathbf{W}_{i})z_{t2}(\mathbf{x}_{i},\mathbf{W}_{i})^{\prime}}\right)\left({\frac{1}{n}\sum_{i,t}z_{t2}(\mathbf{x}_{i},\mathbf{W}_{i})z_{t2}(\mathbf{x}_{i},\mathbf{W}_{i})^{\prime}}\right)^{-1}$

be the sample projection matrix of $z_{t1}$ onto $z_{t2}$. Define
$\tilde{z}_{t}(\mathbf{x}_{i},\mathbf{w})=z_{t1}(\mathbf{x}_{i},\mathbf{w})-\hat{\Gamma}z_{t2}(\mathbf{x}_{i},\mathbf{w})$.
Consider the regression specification defined by
$\Lambda_{1},\tilde{z}_{t}(\cdot)$. Then the estimated potential weights
associated with the two regression specifications are the same.

###### Proof.

The proof entirely follows from the proof of Theorem B.1 by setting
$\pi_{i}^{*}(\mathbf{w})=\mathbbm{1}(\mathbf{w}=\mathbf{W}_{i})$. ∎

######  Theorem B.3 (Invariance under reparameterization).

Consider a population regression specification in the sense of 2.1. Consider
an invertible matrix $M$ and another population specification defined by
$\tilde{z}_{t}(\mathbf{x}_{i},\mathbf{w})=Mz_{t}(\mathbf{x}_{i},\mathbf{w})$
and $\tilde{\Lambda}=\Lambda M^{\prime}$, so that the two vectors of
coefficients represent the same underlying contrasts. Then the potential
weights associated with the two regression specifications are the same. The
estimated potential weights are also the same.

###### Proof.

We can easily see that the second regression specification has Gram matrix
$\tilde{G}_{n}=MG_{n}M^{\prime}$ (and
$\widehat{\tilde{G}_{n}}=M\hat{G}_{n}M^{\prime}$). Thus the potential weights
for the second specification are

$\tilde{\bm{\rho}}_{it}(\mathbf{w})=\tilde{\Lambda}(M^{\prime})^{-1}G_{n}^{-1}M^{-1}Mz_{t}(\mathbf{x}_{i},\mathbf{w})=\bm{\rho}_{it}(\mathbf{w}).$

The corresponding equalities similarly hold for the estimated potential
weights. ∎

###  B.2. Consistency of $\hat{G}_{n}$ to $G_{n}$ under rejective sampling

This subsection considers a law of large numbers under a version of sampling
with replacement (what Hájek, 1964, calls “rejective sampling”), and largely
follows Rambachan and Roth (2020). In particular, we assume that the treatment
is binary, and there is a sequence of unconditional probabilities
$p_{1},p_{2},\ldots$ as well as a sequence of sample sizes $N_{n}$ such that
$\Pi^{*}_{n}$ describes the joint distribution of $W_{1},\ldots,W_{n}$
conditional on the event $\sum_{i=1}^{n}W_{i}=N_{n}$, where
$W_{i}\sim\operatorname{Bern}(p_{i})$ independently unconditionally.
Correspondingly, let $\pi_{i,n}$ be the probability that $W_{i}=1$ under
$\Pi^{*}_{n}$.

######  Lemma B.4.

Write $\pi_{i}(w)=\pi_{i,n}(w)$ and omit the $n$ subscript. Consider
$\overline{y}_{w}=\frac{1}{n}\sum_{i}\mathbbm{1}(W_{i}=w)y_{i}$ where
$\mathbb{E}[\overline{y}_{w}]=\frac{1}{n}\sum_{i}\pi_{i}(w)y_{i}(w)$. Suppose
$C_{n}\equiv\sum_{i=1}^{n}\pi_{i}(w)(1-\pi_{i}(w))\to\infty$ as $n\to\infty$.
Then, as $n\to\infty$

$\operatorname{Var}(\overline{y}_{w})=\frac{(1+o(1))}{n}\frac{C_{n}}{n}\sum_{i=1}^{n}\frac{\pi_{i}(w)(1-\pi_{i}(w))}{C_{n}}\left({y_{i}(w)-\frac{\sum_{j=1}^{n}\pi_{j}(w)(1-\pi_{j}(w))y_{j}(w)}{C_{n}}}\right)^{2}$

###### Proof.

This is a restatement of Theorem 6.1 in Hájek (1964). The notation $y_{i}$ in
the theorem corresponds to $\pi_{i}(w)y_{i}(w)$ in our notation. ∎

A sufficient condition for the variance to tend to zero is the following:

######  Assumption B.1.

For all entries $k$, $z_{k}(x_{i},w)$ is uniformly bounded by $0<M<\infty$ and
$C_{n}(w)\equiv\sum_{i=1}^{n}\pi_{i}(w)(1-\pi_{i}(w))\to\infty$ as
$n\to\infty$.

The boundedness condition for $z_{k}$ is stronger than needed. In particular,
what is needed is that the $\pi_{i}(w)(1-\pi_{i}(w))$-weighted variance of
$y_{i}(w)$ is $O(1)$.

######  Lemma B.5.

Under rejective sampling, suppose Assumption B.1 holds, then
$\hat{G}_{n}\overset{p}{\longrightarrow}G_{n}$ in probability.

###### Proof.

We prove this claim by showing all entries converge in probability, since
there are finitely many entries. Fix some $j,k$. Note that

$\hat{G}_{n,jk}=\sum_{w\in\left\\{{0,1}\right\\}}\underbrace{\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}(W_{i}=w)z_{j}(x_{i},w)z_{k}(x_{i},w)}_{\overline{z}_{n}(w)}.$

By Lemma B.4 and Assumption B.1 applied to $\overline{z}_{n}$ where $y_{i}(w)$
is taken to be $z_{j}(x_{i},w)z_{k}(x_{i},w)$, we have that
$\operatorname{Var}(\overline{z}_{n}(w))\to 0$ as $n\to\infty$, since
$C_{n}(w)/n\leq 1$. Since
$\mathbb{E}[\overline{z}_{n}(w)]=\frac{1}{n}\sum_{i}\pi_{i}(w)z_{j}(x_{i},w)z_{k}(x_{i},w)$,
we have that

$\hat{G}_{n,jk}-G_{n,jk}=\sum_{w\in\left\\{{0,1}\right\\}}\left\\{{\overline{z}_{n}(w)-\frac{1}{n}\sum_{i}\pi_{i}(w)z_{j}(x_{i},w)z_{k}(x_{i},w)}\right\\}\overset{p}{\longrightarrow}0$

by Chebyshev’s inequality. ∎

###  B.3. Uniqueness of implicit designs in cross-sections

Consider a cross-sectional setup with $J+1$ treatments where the potential
weights are

$\rho_{i}(w)=\tilde{\Lambda}\tilde{G}_{n}^{-1}\tilde{z}(x_{i},w)$

and $\tilde{\Lambda}$ is a $J\times K$ matrix with rank $J$. It is possible to
reparametrize the regressors (i.e. choose an invertible $M$ such that
$z(\cdot)=M\tilde{z}(\cdot)$) such that

$\rho_{i}(w)=\Lambda G_{n}^{-1}z(x_{i},w)$

and $\Lambda=[I_{J},0]$. Without essential loss of generality, let us assume
the sequence of reparametrized specifications satisfy Assumption 3.2.

Partition $z$ into $z_{1}$ and $z_{2}$ where $z_{1}$ is $J$-dimensional. By
Theorem B.1, the potential weights are further equivalent to

$\rho_{i}(w)=G_{n,1|2}^{-1}z_{1|2}(x_{i},w)$

where $z_{1|2}(x_{i},w)=z_{1}(x_{i},w)-\Gamma^{\prime}z_{2}(x_{i},w)$ for
population projection coefficients $\Gamma$ and

$G_{n,1|2}=\frac{1}{n}\sum_{i,w}\pi_{i}^{*}(w)z_{1|2}(x_{i},w)z_{1|2}(x_{i},w)^{\prime}.$

######  Assumption B.2.

The residualized covariate transform is non-singular in the sense that the
$J\times(J+1)$ matrix

$Z_{i}\equiv[z_{1|2}(x_{i},0),\ldots,z_{1|2}(x_{i},J)]$

whose columns are covariate transforms evaluated at a treatment level has
minimum singular value greater than some $\eta>0$, uniformly for all $i$.

######  Assumption B.3.

The maximum eigenvalue of $G_{n}$ is bounded above by $M<\infty$ for all $n$.

######  Lemma B.6.

Under Assumptions B.2, 3.2, and B.3, condition (ii) in Proposition 3.5 is
satisfied for some lower bound on the minimum (i.e. $J$th) singular value.

Note that since the potential weight matrix $G_{n,1|2}^{-1}Z_{i}$ is $J\times
J+1$ and has $J$ positive singular values bounded below, if there exists an
implicit design, then it must be unique.

###### Proof.

We first show that Assumption 3.2 is sufficient to show that the minimum
eigenvalue of $G_{n,1|2}$ is bounded away from zero and maximum bounded by
$M$. Note that $G_{n,1|2}$ is a Schur complement of a submatrix of $G_{n}$.
Since $G_{n,1|2}^{-1}$ is a principal submatrix of $G_{n}^{-1}$, the
eigenvalues of $G_{n,1|2}^{-1}$ interlace the eigenvalues of $G_{n}^{-1}$ by
Cauchy’s interlace theorem. In particular, the spectrum of $G_{n,1|2}^{-1}$ is
included in the range of the spectrum of $G_{n}^{-1}$. Hence
$\lambda_{\min}(G_{n,1|2})>\epsilon$ by Assumption 3.2 and
$\lambda_{\max}(G_{n,1|2})<M$ by Assumption B.3.

Next, it suffices to show that $G_{n,1|2}^{-1}Z_{i}$ has minimum singular
value bounded below. Write

$Z_{i}=U\Sigma V^{\prime}$

for diagonal $J\times J$ matrix $\Sigma$ with
$UU^{\prime}=U^{\prime}U=V^{\prime}V=I_{J}$. Similarly, write

$G_{n,1|2}^{-1}=QDQ^{\prime}$

for an orthogonal matrix $Q$ and diagonal $D$. Then

$G_{n,1|2}^{-1}Z_{i}Z_{i}^{\prime}G_{n,1|2}^{-1}=QDQ^{\prime}U\Sigma^{2}U^{\prime}QDQ^{\prime}.$

is a real symmetric matrix. The spectrum of this matrix is the same as the
spectrum of

$D\underbrace{Q^{\prime}U\Sigma^{2}U^{\prime}Q}_{\text{positive definite
matrix with spectrum $\Sigma^{2}$}}D.$

Since $\lambda_{\min}(AB)\geq\lambda_{\min}(A)\lambda_{\min}(B)$ for two
positive definite matrices $A,B$,393939To see this, note that the operator
norm (largest eigenvalue) is submultiplicative $\lVert AB\rVert_{op}\leq\lVert
A\rVert_{op}\lVert B\rVert_{op}$. Apply this inequality to $A^{-1}B^{-1}$. we
have that the minimum eigenvalue of
$G_{n,1|2}^{-1}Z_{i}Z_{i}^{\prime}G_{n,1|2}^{-1}$ is bounded below by
$\frac{\eta^{2}}{\lambda_{\max}(G_{n,1|2})^{2}}$. Thus, the minimum singular
value of $G_{n,1|2}^{-1}Z_{i}$ is bounded below by $\eta/M$. ∎

###  B.4. Additional results for cross-sectional specifications

######  Proposition B.7.

Consider the cross-sectional specification $Y_{i}=\tau
W_{i}+\gamma^{\prime}x_{i}+\epsilon_{i}$ and a sample
$(Y_{i},W_{i},x_{i})_{i=1}^{n}$. Suppose $x_{i}$ includes a constant. Suppose
$\hat{G}_{n}$ is invertible on this realization. Let $\hat{\gamma}_{w\to x}$
be the OLS coefficient of $W_{i}$ on $x_{i}$, and let $\hat{\pi}_{i}$ be the
OLS fitted value $\hat{\pi}_{i}=\hat{\gamma}_{w\to x}^{\prime}x_{i}$. Then:

  1. (i)

The potential weights are

$\hat{\rho}_{i}(w)=\frac{W_{i}-\hat{\pi}_{i}}{\frac{1}{n}\sum_{i=1}^{n}\hat{\pi}_{i}(1-\hat{\pi}_{i})}$

and $\frac{1}{n}\sum_{i=1}^{n}\hat{\pi}_{i}(1-\hat{\pi}_{i})>0$.

  2. (ii)

The estimated implicit design exists and is uniquely equal to $\hat{\pi}_{i}$.

###### Proof.

(i) follows from Theorem B.2 immediately, upon verifying that

$0<\frac{1}{n}\sum_{i=1}^{n}(W_{i}-\hat{\pi}_{i})^{2}=\frac{1}{n}\sum_{i=1}^{n}\hat{\pi}_{i}(1-\hat{\pi}_{i}).$

The equality follows because

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}(W_{i}-\hat{\pi}_{i})^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}W_{i}-2W_{i}\hat{\pi}_{i}+\hat{\pi}_{i}^{2}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\hat{\pi}_{i}-2(W_{i}-\hat{\pi}_{i})\hat{\pi}_{i}-2\hat{\pi}_{i}^{2}+\hat{\pi}_{i}^{2}$
($\frac{1}{n}\sum_{i}\hat{\pi}_{i}=\frac{1}{n}\sum_{i}W_{i}$ since $x_{i}$
includes a constant)
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\hat{\pi}_{i}-\hat{\pi}_{i}^{2}$
($\frac{1}{n}\sum_{i=1}^{n}(W_{i}-\hat{\pi}_{i})\hat{\pi}_{i}=0$ by
orthogonality of residuals)
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\hat{\pi}_{i}(1-\hat{\pi}_{i}).$

For (ii), note that the implicit design is equal to

$-\rho_{i}(0)/(\rho_{i}(1)-\rho_{i}(0))=\hat{\pi}_{i}$

uniquely by 2.2. ∎

######  Proposition B.8.

Consider the specification (4.1.2) where $x_{i}$ is a saturated vector of
underlying categorical covariates. That is, suppose
$c_{i}\in\left\\{{0,\ldots,L}\right\\}$ and $x_{i}$ is a vector such that
$x_{i\ell}=\mathbbm{1}(c_{i}=\ell)$ for $\ell=1,\ldots,L$. Then the only
implicit design sets $\pi_{i}$, for $c_{i}=\ell$, to be the mean $\pi_{j}^{*}$
among those $j$ with $c_{j}=\ell$. The corresponding implicit estimand is the
average treatment effect.

###### Proof.

The specification (4.1.2) is equivalent to the following specification:

$Y_{i}=\sum_{\ell=0}^{L}\alpha_{\ell}+\tau_{\ell}W_{i}$

where
$\tau=\left({1-\sum_{\ell=1}^{L}\overline{x}_{\ell}}\right)\tau_{0}+\sum_{\ell=1}^{L}\overline{x}_{\ell}\tau_{\ell}\equiv\sum_{\ell=0}^{L}\overline{x}_{\ell}\tau_{\ell}$.

For this specification, let us order the covariates to be

$[\mathbbm{1}(c_{i}=0),\mathbbm{1}(c_{i}=0)W_{i},\mathbbm{1}(c_{i}=1),\mathbbm{1}(c_{i}=1)W_{i},\ldots,\mathbbm{1}(c_{i}=L),\mathbbm{1}(c_{i}=L)W_{i}].$

Note that the population Gram matrix is of the form

$G_{n}=\begin{bmatrix}G_{0}\\\ &G_{1}\\\ &&\ddots\\\ &&&G_{L}\end{bmatrix}$

where

$G_{\ell}=\begin{bmatrix}\overline{x}_{\ell}&\overline{x}_{\ell}\pi(\ell)\\\
\overline{x}_{\ell}\pi(\ell)&\overline{x}_{\ell}\pi(\ell)\end{bmatrix}$

where $\pi(\ell)$ is the mean of $\pi_{i}^{*}$ among those with $c_{i}=\ell$.
Since $G_{n}$ is block-diagonal, its inverse is similarly block-diagonal with

$G_{\ell}^{-1}=\frac{1}{\overline{x}_{\ell}\pi(\ell)(1-\pi(\ell))}\begin{bmatrix}\pi(\ell)&-\pi(\ell)\\\
-\pi(\ell)&1\end{bmatrix}$

on the diagonal. Note that
$\lambda=[0,\overline{x}_{0},0,\overline{x}_{1},\ldots,0,\overline{x}_{L}]^{\prime}$.
Thus

$\lambda^{\prime}G_{n}^{-1}=\left[{\frac{-\pi(0)}{\pi(0)(1-\pi(0))},\frac{1}{\pi(0)(1-\pi(0))},\ldots,\frac{-\pi(L)}{\pi(L)(1-\pi(L))},\frac{1}{\pi(L)(1-\pi(L))}}\right].$

For someone with $c_{i}=\ell$, the covariate transform is of the form

$z(x_{i},w)=[0,\ldots,0,1,w,0,\ldots,0]^{\prime}$

where it is nonzero at the $\ell$th pair. Thus

$\rho_{i}(w)=\lambda^{\prime}G_{n}^{-1}z(x_{i},w)=\frac{w-\pi(\ell)}{\pi(\ell)(1-\pi(\ell))}.$

By 2.2, the only implicit design sets $\pi_{i}=\pi(\ell)$ for $c_{i}=\ell$.
Note that the implicit design is described by
$\omega_{i}=\pi(\ell)\rho_{i}(1)=1.$ Therefore the implicit estimand is the
average treatment effect. ∎

###  B.5. Additional results for panel specifications

######  Proposition B.9 (One-way fixed effects).

Consider the regression $Y_{it}=\alpha_{i}+\tau W_{it}+\epsilon_{it}$. If
$\mathcal{W}$ satisfies staggered adoption without an always treated unit,
then the set of implicit designs is empty.

###### Proof.

Let $\dot{\mathbf{w}}=\mathbf{w}-1_{T}\frac{1_{T}^{\prime}\mathbf{w}}{T}$.
Then the potential weights are equal to

$\rho_{i}(w)=\frac{\dot{\mathbf{w}}}{\frac{1}{n}\sum_{i=1}^{n}\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}^{*}(\mathbf{w})\dot{\mathbf{w}}^{\prime}\dot{\mathbf{w}}}.$

Thus, if $\pi_{i}$ corresponds to some implicit design $\bm{\pi}$,

$\sum_{\mathbf{w}\in\mathcal{W}}\pi_{i}(\mathbf{w})\left({\mathbf{w}-1_{T}\frac{1_{T}^{\prime}\mathbf{w}}{T}}\right)=0.$

In particular, this implies that $1_{T}$ is in the linear span of
$\mathcal{W}$. By assumption, this is not the case. Therefore the set of
implicit designs must be empty. ∎

Intuitively, this is because one-way fixed effects fail to account for the
case where the treatment path correlates with underlying potential outcomes.
If there are no treatment effects whatsoever, but the baseline potential
outcome correlates with the treatment path (e.g., later potential outcomes
tend to be larger in staggered adoption), then one-way fixed effects would in
general estimate a nonzero coefficient, violating level irrelevance.

These results contrast with the results in Arkhangelsky and Imbens (2023b),
where the one-way fixed effect regression admits a design-based interpretation
under within-unit random assignment of $W_{it}$. To reconcile, Arkhangelsky
and Imbens (2023b) consider a sampling-based setup and the unconfoundedness
restriction

$W_{it}\indep(Y_{it}(0),Y_{it}(1))\mid\frac{1}{T}\sum_{s=1}^{T}W_{is},$

which is their (2.2) in our notation. In staggered adoption, however, the
associated propensity score
$\operatorname{P}\left({W_{it}=1\mid\frac{1}{T}\sum_{s=1}^{T}W_{is}}\right)$
is always degenerate, since $\frac{1}{T}\sum_{s=1}^{T}W_{is}$ perfectly
distinguishes which treatment path unit $i$ is assigned. Conversely, if
$W_{it}$ is randomly assigned within a unit and that permuting the time index
results in valid counterfactual assignments, then $\mathcal{W}$ is large
enough to contain $1_{T}$.

######  Proposition B.10.

Consider the TWFE specification $Y_{it}=\alpha_{i}+\gamma_{t}+\tau W_{it}$
under staggered adoption. Suppose the treatment time is randomly assigned so
that $\pi_{i}^{*}(\mathbf{w})=\pi^{*}(\mathbf{w})$. If there are two treatment
paths with one being never-treated,
$\mathbf{W}=\left\\{{0,\mathbf{w}}\right\\}$, then
$\bm{\rho}_{it}(\mathbf{w})\geq 0$ for all post treatment periods
$\mathbf{w}_{t}=1$ and $i\in[n]$. Otherwise, in all other configurations where
$|\mathcal{W}|\geq 2$, there exists a choice of $\pi^{*}(\mathbf{w})$ such
that $\bm{\rho}_{it}(\mathbf{w})<0$ for some treatment path $\mathbf{w}$ with
positive assignment probability ($\pi^{*}(\mathbf{w})>0$) and some post-
treatment period $t$ ($\mathbf{w}_{t}=1$).

###### Proof.

The potential weight can be computed in closed form. For some $V>0$,

$\bm{\rho}_{it}(\mathbf{w})=V^{-1}\left[{\mathbf{w}_{t}-\frac{1^{\prime}}{T}\mathbf{w}-\sum_{\tilde{\mathbf{w}}\in\mathcal{W}}\pi^{*}(\tilde{\mathbf{w}})\tilde{\mathbf{w}}_{t}+\sum_{\tilde{\mathbf{w}}\in\mathcal{W}}\pi^{*}(\tilde{\mathbf{w}})\frac{1^{\prime}}{T}\tilde{\mathbf{w}}}\right].$

When $\mathcal{W}=\left\\{{0,\mathbf{w}}\right\\}$, then for a post-treatment
$t$,

$\bm{\rho}_{it}(\mathbf{w})=V^{-1}(1-\pi^{*}(\mathbf{w}))(1-1^{\prime}\mathbf{w}/T)\geq
0.$

Otherwise, let $\mathbf{w}$ be the treatment path with the earliest adoption
date, and consider $t=T$. By assumption, $\mathcal{W}$ contains a path that
adopts later than $\mathbf{w}$. Then

$\bm{\rho}_{it}(\mathbf{w})=V^{-1}\left({(1-\pi^{*}(\mathbf{w}))(1-1^{\prime}\mathbf{w}/T)-\sum_{\tilde{\mathbf{w}}\neq\mathbf{w}}\pi^{*}(\tilde{\mathbf{w}})\left({1-1^{\prime}\tilde{\mathbf{w}}/T}\right)}\right)$

Pick $\pi^{*}(\mathbf{w})=1/2=\pi^{*}(\tilde{\mathbf{w}})$ where
$\tilde{\mathbf{w}}$ adopts later than $\mathbf{w}$. Then

$\bm{\rho}_{it}(\mathbf{w})=V^{-1}\left({1/2(1-1^{\prime}\mathbf{w}/T)-1/2\left({1-1^{\prime}\tilde{\mathbf{w}}/T}\right)}\right)=\frac{1}{2}V^{-1}1^{\prime}(\tilde{\mathbf{w}}-\mathbf{w})/T<0$

since $\tilde{\mathbf{w}}$ adopts later than $\mathbf{w}$. ∎


#  Maximum values of the edge Mostar index in tricyclic graphs

Fazal Hayata, Shou-Jun Xua,b111Corresponding author
E-mail addresses<EMAIL_ADDRESS>(F. Hayat<EMAIL_ADDRESS>(S. J.
Xu<EMAIL_ADDRESS>(B. Zhou), Bo Zhouc
aSchool of Mathematics and Statistics, Gansu Center for Applied Mathematics,
Lanzhou University, Lanzhou 730000, P.R. China
bSchool of Mathematics and Statistics, Minnan Normal University,
Zhangzhou, Fujian 363000, P.R. China
cSchool of Mathematical Sciences, South China Normal University,
Guangzhou 510631, P.R. China

###### Abstract

For a graph $G$, the edge Mostar index of $G$ is the sum of
$|m_{u}(e|G)-m_{v}(e|G)|$ over all edges $e=uv$ of $G$, where $m_{u}(e|G)$
denotes the number of edges of $G$ that have a smaller distance in $G$ to $u$
than to $v$, and analogously for $m_{v}(e|G)$. This paper mainly studies the
problem of determining the graphs that maximize the edge Mostar index among
tricyclic graphs. To be specific, we determine a sharp upper bound for the
edge Mostar index on tricyclic graphs and identify the graphs that attain the
bound.

Keywords: Mostar index, edge Mostar index, tricyclic graph, extremal graph.

2010 Mathematics Subject Classification: 05C12; 05C35; 05C38

##  1 Introduction

Let $G=(V,E)$ be a graph with vertex set $V(G)$ and edge set $E(G)$. The order
and size of $G$ are the cardinality of $V(G)$ and $E(G)$, respectively. The
distance between $u$ and $v$ in $G$ is the least length of the path connecting
$u$ and $v$ denoted by $d_{G}(u,v)$. For a vertex $x$ and edge $e=uv$ of a
graph $G$, the distance between $x$ and $e$, denoted by $d_{G}(x,e)$ , is
defined as $d_{G}(x,e)=min\\{d_{G}(x,u),d_{G}(x,v)\\}$.

A topological index is a real number related to graph $G$. They are widely
used for characterizing molecular graphs, establishing relationships between
structure and properties of molecules, predicting biological activity of
chemical compounds, and making their chemical applications.

Došlić et al. [7] introduced a bond-additive structural invariant as a
quantitative refinement of the distance non-balancedness and also a measure of
peripherality in graphs, named the Mostar index. For a graph $G$, the Mostar
index is defined as

$Mo(G)=\sum_{e=uv\in E(G)}|n_{u}(e|G)-n_{v}(e|G)|.$

where $n_{u}(e|G)$ is the number of vertices of $G$ closer to $u$ than to $v$
and $n_{v}(e|G)$ is the number of vertices closer to $v$ than to $u$.

The problem of determining which graphs uniquely maximize (resp. minimize) the
Mostar index in some classes of graphs has received much attention. For
example, Došlić et al. [7] studied the Mostar index of trees and unicyclic
graphs, and gave a cut method for computing the Mostar index of benzenoid
systems. Hayat and Zhou [14] determined all the $n$-vertex cacti with the
largest Mostar index, and obtained a sharp upper bound for the Mostar index
among cacti of order $n$ with $k$ cycles, and characterized the extremal
cacti. Hayat and Zhou [15] identified those trees with minimum and/or maximum
Mostar index in the families of trees of order $n$ with fixed parameters like
maximum degree, diameter and the number of pendent vertices. Hayat and Xu [11]
determined the graphs that maximize and minimize the Mostar index among trees
of order $n$, and one of the fixed parameters such as, odd vertices, vertices
of degree two, and pendent paths of fixed length. Hayat and Xu [12] obtained a
lower bound on the Mostar index in tricyclic graphs, and characterized the
graphs that attain the bound. Deng and Li [3] determined those trees with a
given degree sequence have a maximum Mostar index. The Mostar index among
trees with a given number of segment sequence hve been studied in [4]. For
more studies about the Mostar index see [2, 5, 6, 16, 18, 20, 21, 22].

Arockiaraj et al. [1], introduced the edge Mostar index as a quantitative
refinement of the distance non-balancedness, also it can measure the
peripherality of every edge and consider the contributions of all edges into a
global measure of peripherality for a given chemical graph. The edge Mostar
index of $G$ is defined as

$Mo_{e}(G)=\sum_{e=uv\in E(G)}\psi_{G}(uv),$

where $\psi_{G}(uv)=|m_{u}(e|G)-m_{v}(e|G)|$, and $m_{u}(e|G)$ denotes the
number of edges of $G$ that have a smaller distance in $G$ to $u$ than to $v$,
and analogously for $m_{v}(e|G)$.

Imran et al. [17] studied the edge Mostar index of chemical structures and
nanostructures using graph operations. Liu et al. [19] determined the extremal
values of the edge Mostar index among trees and unicyclic graphs and
determined the maximum and the second maximum value of the edge Mostar index
among cactus graphs with a given number of vertices. Ghalavand et al. [8]
determined the minimum values of the edge Mostar index among bicyclic graphs
with fixed size, and characterized the corresponding extremal graphs. The edge
Mostar index for several classes of cycle-containing graphs was computed in
[10]. Recently, Hayat et al. [13] determined the sharp upper bound for the
edge Mostar index on bicyclic graphs with a fixed number of edges, and the
graphs that achieve the bound are completely characterized. Ghanbari and
Alikhani [9] computed the Mostar and edge Mostar index for polymers.

To have a full understanding of the relationship between the edge Mostar index
and the structural properties of the graphs, in this paper, we consider the
edge Mostar index among tricyclic graphs, more precisely, we obtain the sharp
upper bound for the edge Mostar index on tricyclic graphs with a fixed number
of edges, and characterize all the graphs that attain the bound.

Figure 1:  The Graphs $A_{i}$ $(i=0,1,...,6)$ of size $m$ in Theorem 1.1.

######  Theorem 1.1.

Let $G$ be a tricyclic graph of size $m$. Then

$Mo_{e}(G)\leq\left\\{\begin{array}[]{ll}12,&\hbox{if $m=7$, and equality
holds iff $G\cong F_{1},H_{1}$};\\\ 23,&\hbox{if $m=8$, and equality holds iff
$G\cong A_{3},F_{1},H_{1}$};\\\ 36,&\hbox{if $m=9$, and equality holds iff
$G\cong F_{1},H_{1},A_{i}(i=2,...,6)$};\\\ 53,&\hbox{if $m=10$, and equality
holds iff $G\cong A_{2}$};\\\ 72,&\hbox{if $m=11$, and equality holds iff
$G\cong A_{1},A_{2}$};\\\ m^{2}-m-36,&\hbox{if $m\geq 12$, and equality holds
iff $G\cong A_{0}$}.\end{array}\right.$

(Where $A_{i}$ $(i=0,1,...,6)$ are depicted in Fig. 1.1, $F_{1},H_{1}$ are
depicted and Fig. 6 and Fig. 7, respectively).

In section 2, we give some definitions and preliminary results. Theorem 1.1 is
proved in section 3.

##  2 Preliminaries

In this section, some basic notations and elementary results are listed, which
will be useful in the proof of main results.

Figure 2:  The braces in $\mathcal{G}_{m}$.

For $v\in V(G)$, let $N_{G}(v)$ be the set of vertices that are adjacent to
$v$ in $G$. The degree of $v\in V(G)$ , denoted by $d_{G}(v)$, is the
cardinality of $N_{G}(v)$. A vertex with degree one is called a pendent vertex
and an edge incident to a pendent vertex is called a pendent edge. A graph $G$
with $n$ vertices is a tricyclic graph if $|E(G)|=n+2$. As usual, by $S_{n}$,
$P_{n}$ and $C_{n}$ we denote the star, path and cycle on $n$ vertices,
respectively.

Let $G_{1}\cdot G_{2}$ be the graph obtained from $G_{1}$ and $G_{2}$ by
identifying one vertex, say $u$ of the two graphs. If $G_{1}$ contains a cycle
and $u$ belongs to some cycle, and $G_{2}$ is a tree, then we call $G_{2}$ a
pendent tree in $G_{1}\cdot G_{2}$ associated with $u$. For each $e\in
E(G_{1})$, every path from $e$ to some edges of $G_{2}$ passes through $u$.
Therefore, the contribution of $G_{2}$ to $\sum_{e\in E(G_{1})}\psi(e)$
totally depends on the size of $G_{2}$, that is, changing the structure of
$G_{2}$ cannot alter the value $\sum_{e\in E(G_{1})}\psi(e)$. If a graph $H$
is gotten by removing repeatedly all pendents (If any) of $G$. Then we say $H$
is the brace of $G$. That is to say, $H$ does not contain any pendent vertex.
Obviously, for all connected tricyclic graphs, their braces are shown in Fig.
2. Let $\mathcal{G}_{m}^{i}$ be the collection whose element includes
$\alpha_{i}$ as its brace for $i=1,\dots,15$. For convenience, let
$\mathcal{A}=\cup_{i=5}^{15}\mathcal{G}_{m}^{i}$.

In the following, Hayat et al. [13] determined a sharp upper bound for the
edge Mostar index on bicyclic graphs with a fixed number of edges

######  Theorem 2.1.

Let $G$ be a bicyclic graph of size $m$. Then

$Mo_{e}(G)\leq\left\\{\begin{array}[]{ll}4,&\hbox{if $m=5$, and equality holds
iff $G\cong B_{3},B_{4}$};\\\ m^{2}-3m-6,&\hbox{if $6\leq m\leq 8$, and
equality holds iff $G\cong B_{1},B_{3}$};\\\ 48,&\hbox{if $m=9$, and equality
holds iff $G\cong B_{0},B_{1},B_{2},B_{3},B_{4}$};\\\ m^{2}-m-24,&\hbox{if
$m\geq 10$, and equality holds iff $G\cong B_{0}$}.\end{array}\right.$

(Where $B_{0},B_{1},B_{2},B_{3},B_{4}$ are depicted in Fig. 3).

Let $S_{m,r}\cong S_{m-r}\cdot C_{r}$, where the common vertex of $S_{m-r}$
and $C_{r}$ is the center of $S_{m-r}$.

######  Lemma 2.1.

[13] Let $G_{1}$ be a connected graph of size $m_{1}$ and $G_{2}$ be a
unicyclic graph of size $m_{2}$. Then

$Mo_{e}(G_{1}\cdot G_{2})\leq Mo_{e}(G_{1}\cdot S_{m_{2},3})$ for
$m_{1}+m_{2}\leq 8$;

$Mo_{e}(G_{1}\cdot G_{2})\leq Mo_{e}(G_{1}\cdot S_{m_{2},3})=Mo_{e}(G_{1}\cdot
S_{m_{2},4})$ for $m_{1}+m_{2}=9$;

$Mo_{e}(G_{1}\cdot G_{2})\leq Mo_{e}(G_{1}\cdot S_{m_{2},4})$ for
$m_{1}+m_{2}\geq 10$;

where the fusing vertex of $G_{1}\cdot S_{m_{2},3}$ (resp. $G_{1}\cdot
S_{m_{2},4}$) is the center of $S_{m_{2},3}$ (resp. $S_{m_{2},4}$).

By means of Theorem 2.1 and the above result, the following conclusions are
obtained.

######  Lemma 2.2.

Let $G=G_{1}\cdot G_{2}$ be a tricyclic graph, where $G_{1}$ is a bicyclic
graph of size $m_{1}$ and $G_{2}$ is a unicyclic graph of size $m_{2}$. Then

$Mo_{e}(G)\leq Mo_{e}(B_{3}\cdot S_{m_{2},3})$ for $m_{1}+m_{2}=8$;

$Mo_{e}(G)\leq Mo_{e}(B_{2}\cdot S_{m_{2},3})=Mo_{e}(B_{3}\cdot
S_{m_{2},3})=Mo_{e}(B_{3}\cdot S_{m_{2},4})=Mo_{e}(B_{4}\cdot
S_{m_{2},3})=Mo_{e}(B_{4}\cdot S_{m_{2},4})$ for $m_{1}+m_{2}=9$;

$Mo_{e}(G)\leq Mo_{e}(B_{0}\cdot S_{m_{2},4})$ for $m_{1}+m_{2}\geq 12$;

where the fusing vertex of any of the above two graphs is the center of
$S_{m_{2},3}$ or $S_{m_{2},4}$.

Figure 3: The Graphs $B_{i}$ $(i=0,1,...,4)$ of size $m$ in Theorem 2.1.

##  3 Proof of Theorem 1.1

For the proof of Theorem 1.1, we first develop several lemmas.

First, we obtain a sharp upper bound for $Mo_{e}(G)$ on
$\mathcal{A}=\cup_{i=5}^{15}\mathcal{G}_{m}^{i}$.

######  Lemma 3.1.

Let $G\in\mathcal{A}$ of size $m$. Then

$Mo_{e}(G)\leq\left\\{\begin{array}[]{ll}23,&\hbox{if $m=8$, and equality
holds iff $G\cong A_{3}$};\\\ 36,&\hbox{if $m=9$, and equality holds iff
$G\cong A_{i}(i=2,...,6)$};\\\ 53,&\hbox{if $m=10$, and equality holds iff
$G\cong A_{2}$};\\\ 72,&\hbox{if $m=11$, and equality holds iff $G\cong
A_{1},A_{2}$};\\\ m^{2}-m-36,&\hbox{if $m\geq 12$, and equality holds iff
$G\cong A_{0}$};\end{array}\right.$

###### Proof.

Suppose $G\in\mathcal{A}$, then $G$ contains $\alpha_{i}(i=5,6,...,15)$ as its
brace. Let $G_{1}$ be a bicyclic graph of size $m_{1}$ and $G_{2}$ be a
unicyclic graph of size $m_{2}$ such that $G=G_{1}\cdot G_{2}$. Then, in view
of Lemmas 2.1 and 2.2, if $m=8$, we get

$\displaystyle Mo_{e}(G)$ $\displaystyle=$ $\displaystyle Mo_{e}(G_{1}\cdot
G_{2})\leq Mo_{e}(G_{1}\cdot S_{m_{2},3})$ $\displaystyle\leq$ $\displaystyle
Mo_{e}(B_{3}\cdot S_{m_{2},3})=Mo_{e}(A_{3});$

if $m=9$, we get

$\displaystyle Mo_{e}(G)$ $\displaystyle=$ $\displaystyle Mo_{e}(G_{1}\cdot
G_{2})\leq Mo_{e}(B_{2}\cdot S_{m_{2},3})=Mo_{e}(B_{3}\cdot S_{m_{2},3})$
$\displaystyle=$ $\displaystyle Mo_{e}(B_{3}\cdot
S_{m_{2},4})=Mo_{e}(B_{4}\cdot S_{m_{2},3})=Mo_{e}(B_{4}\cdot S_{m_{2},4})$
$\displaystyle=$ $\displaystyle Mo_{e}(A_{i})(i=2,...,6);$

if $m\geq 12$, we have

$\displaystyle Mo_{e}(G)$ $\displaystyle=$ $\displaystyle Mo_{e}(G_{1}\cdot
G_{2})\leq Mo_{e}(G_{1}\cdot S_{m_{2},4})$ $\displaystyle\leq$ $\displaystyle
Mo_{e}(B_{0}\cdot S_{m_{2},4})=Mo_{e}(A_{0}).$

By simple calculation, it is easy to check that, $Mo_{e}(A_{0})=m^{2}-m-36$,
$Mo_{e}(A_{1})=Mo_{e}(A_{2})=m^{2}-2m-27$,
$Mo_{e}(A_{3})=Mo_{e}(A_{4})=m^{2}-4m-9$,
$Mo_{e}(A_{5})=Mo_{e}(A_{6})=Mo_{e}(A_{7})=m^{2}-3m-18$.

Clearly, $Mo_{e}(A_{0})=m^{2}-m-36>Mo_{e}(A_{i})(i=3,...,7)$, for $m\geq 10$,
but $A_{0}$ contains at least 12 edges. Therefore, if $m=11$, then
$Mo_{e}(A_{1})=Mo_{e}(A_{2})>Mo_{e}(A_{i})(i=3,...,7)$; if $m=10$, then
$Mo_{e}(A_{2})>A_{i}(i=3,...,7)$. ∎

Figure 4:  The Graphs for Lemmas 3.2, 3.4, 3.5, 3.6, 3.8, 3.9 and 3.10.

In what follows, we determine a sharp upper bound for $Mo_{e}(G)$ on
$\cup_{i=1}^{4}\mathcal{G}_{m}^{i}$.

For $i=1,...,4$, $\alpha_{i}(a_{1},a_{2},\dots)$ represents the number of
edges in each portion of the brace $\alpha_{i}$.

######  Lemma 3.2.

Let $G\in\mathcal{G}_{m}^{1}$ with brace $\alpha_{1}(1,1,1,2,1,1)$. Then

$Mo_{e}(G)<\left\\{\begin{array}[]{ll}Mo_{e}(D_{1})=m^{2}-3m-24,&\hbox{if
$7\leq m\leq 10$};\\\ Mo_{e}(D_{1})=Mo_{e}(D_{2})=64,&\hbox{if $m=11$};\\\
Mo_{e}(D_{2})=m^{2}-2m-35,&\hbox{if $m\geq 12$}.\end{array}\right.$

###### Proof.

Suppose that $v_{i}$ $(i=1,...,5)$ be the vertices in $\alpha_{1}$ of $G$, as
shown in Fig. 4. Let $a_{i}$ be the number of pendent edges of $v_{i}$
$(i=1,...,5)$. Suppose that $a_{1}+a_{3}\geq a_{2}+a_{4}\geq 1$ . Let $G_{1}$
be the graph obtained from $G$ by shifting $a_{2}$ (resp. $a_{4}$) pendent
edges from $v_{2}$ (resp. $v_{4}$) to $v_{1}$ (resp. $v_{3}$). We deduce that

$\displaystyle Mo_{e}(G_{1})-Mo_{e}(G)=$
$\displaystyle(a_{1}+a_{2}-a_{3}-a_{4}-a_{5})-(a_{1}+a_{4}-a_{3}-a_{5})+(a_{3}+a_{4}+a_{5}+2-3)$
$\displaystyle-$
$\displaystyle(a_{2}+a_{4}+3-a_{3}-a_{5}-2)+(a_{3}+a_{4}+a_{5}+2-3)-(a_{2}+a_{4}+3-a_{3}-a_{5}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}-a_{5})-(a_{1}+a_{3}-a_{4}-a_{5})+(a_{3}+a_{4}+3-a_{5}-2)$
$\displaystyle-$
$\displaystyle(a_{2}+a_{3}+3-a_{4}-a_{5}-2)+(a_{3}+a_{4}+3-a_{5}-2)-(a_{2}+a_{3}+3-a_{4}-a_{5}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2})-(a_{1}-a_{2})+(a_{1}+a_{2}+a_{3}+a_{4}+3-a_{5}-1)-(a_{1}+a_{2}+a_{3}+3-a_{4}-a_{5}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+3-a_{3}-a_{4}-a_{5}-1)-(a_{1}+a_{2}+a_{4}+3-a_{3}-a_{5}-1)$
$\displaystyle=$ $\displaystyle 2(a_{2}+a_{3}+a_{4}+a_{5})-2>0.$

For $a_{5}>0$, let $G_{2}$ be the graph obtained from $G_{1}$ by shifting
$a_{5}$ pendent edges from $v_{5}$ to $v_{3}$. We obtain

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{1}+a_{3}+a_{5})-(a_{1}+a_{3}-a_{5})+(a_{3}+a_{5}+3-2)-(a_{3}+3-a_{5}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{5}+3-1)-(a_{1}+a_{3}+3-a_{5}-1)$
$\displaystyle=$ $\displaystyle 6a_{5}>0.$

Let $G_{3}$ be the graph obtained from $G_{2}$ by shifting $a_{1}$ pendent
edges from $v_{1}$ to $v_{3}$. We obtain

$\displaystyle Mo_{e}(G_{3})-Mo_{e}(G_{2})=$
$\displaystyle(a_{1}+a_{3})-(a_{3}-a_{1})+(a_{1}+a_{3}+2-3)-(a_{3}+2-3)+(a_{1}+a_{3}+3-2)-(a_{3}+3-2)$
$\displaystyle+$ $\displaystyle 0-a_{1}+(a_{1}+a_{3}+1-3)-(a_{3}+1-a_{1}-3)$
$\displaystyle=$ $\displaystyle 5a_{1}>0.$

Clearly, $G_{3}\cong D_{2}$, and $G_{2}\cong D_{1}$ for $a_{3}=0$. Observe
that $Mo_{e}(D_{1})=m^{2}-3m-24$, and $Mo_{e}(D_{2})=m^{2}-2m-35$ . ∎

Figure 5:  The Graphs $D_{1},D_{2}$ of size $m$ in Lemma 3.2.

######  Lemma 3.3.

Let $G\in\mathcal{G}_{m}^{1}$ of size $m$. Then $Mo_{e}(G)<m^{2}-m-36$.

###### Proof.

Suppose that $G\in\mathcal{G}_{m}^{1}$, then $G$ has a brace
$\alpha_{1}(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6})$ as shown in Fig. 8. We
consider the following three possible cases.

Case 1. $\alpha_{1}$ have at least three paths with length at least two.

Subcase 1.1. The three paths inclose a cycle.

Assume that the three paths are $P(a_{1}),P(a_{2})$ and $P(a_{6})$ by the
symmetry of $\alpha_{1}$. We choose nine edges, two edges in the path
$P(a_{1})$ such that each one is incident to $x$ or $u$, two edges in the path
$P(a_{2})$ such that each one is incident to $y$ or $u$, two edges in the path
$P(a_{6})$ such that each one is incident to $y$ or $z$, one edge in the path
$P(a_{3})$ incident to $z$, one edge in the path $P(a_{4})$ incident to $z$
and one edge in the path $P(a_{5})$ incident to $z$. Let $e$ be one of the
nine edges. Then $\psi(e)\leq m-7$. This fact is also true for the remaining
eight edges. Thus,

$Mo_{e}(G)\leq 9(m-7)+(m-9)(m-1)<m^{2}-m-36.$

Subcase 1.2. The three paths composed a new path.

Assume that the three paths are $P(a_{1}),P(a_{2})$ and $P(a_{4})$ by the
symmetry of $\alpha_{1}$. We choose nine edges, two edges in the path
$P(a_{1})$ such that each one is incident to $x$ or $u$, two edges in the path
$P(a_{2})$ such that each one is incident to $y$ or $u$, two edges in the path
$P(a_{4})$ such that each one is incident to $y$ or $z$, one edge in the path
$P(a_{3})$ incident to $z$, one edge in the path $P(a_{5})$ incident to $z$
and one edge in the path $P(a_{6})$ incident to $x$. Thus,

$Mo_{e}(G)\leq 2(m-6)+4(m-7)+2(m-8)+(m-9)+(m-9)(m-1)<m^{2}-m-36.$

Subcase 1.3. The three paths share a common vertex.

Assume that the three paths are $P(a_{1}),P(a_{2})$ and $P(a_{3})$ by the
symmetry of $\alpha_{1}$. We choose nine edges, two edges in the path
$P(a_{1})$ such that each one is incident to $x$ or $u$, two edges in the path
$P(a_{2})$ such that each one is incident to $y$ or $u$, two edges in the path
$P(a_{3})$ such that each one is incident to $u$ or $z$, one edge in the path
$P(a_{4})$ incident to $y$, one edge in the path $P(a_{5})$ incident to $z$
and one edge in the path $P(a_{6})$ incident to $x$. We have,

$Mo_{e}(G)\leq 3(m-7)+3(m-8)+3(m-9)+(m-9)(m-1)<m^{2}-m-36.$

Case 2. $\alpha_{1}$ have just two paths with length at least two.

Subcase 2.1. The two paths belong to the same cycle at $\alpha_{1}$.

Assume that the two paths are $P(a_{1})$ and $P(a_{2})$ by the symmetry of
$\alpha_{1}$. We choose eight edges, two edges in the path $P(a_{1})$ such
that each one is incident to $x$ or $u$, two edges in the path $P(a_{2})$ such
that each one is incident to $y$ or $u$, one edge in the path $P(a_{3})$
incident to $u$, one edge in the path $P(a_{4})$ incident to $y$, one edge in
the path $P(a_{5})$ incident to $x$ and one edge in the path $P(a_{6})$
incident to $x$. We deduce that,

$Mo_{e}(G)\leq 4(m-6)+3(m-7)+(m-8)+(m-8)(m-1)<m^{2}-m-36.$

Subcase 2.2. The two paths belong to the two different cycles at $\alpha_{1}$.

We choose eight edges in a similar way, as in Subcase 2.1. We obtain

$Mo_{e}(G)\leq 4(m-5)+4(m-8)+(m-8)(m-1)<m^{2}-m-36.$

Case 3. $\alpha_{1}$ has exactly one path with length at least two.

Assume that the path is $P(a_{4})$ with $a_{4}\geq 2$. If $a_{4}=2$, then by
Lemma 3.2, $Mo_{e}(G)<m^{2}-m-36$. If $a_{4}\geq 3$, then similarly choose
eight edges as in Subcase 2.1. We obtain

$Mo_{e}(G)\leq 2(m-5)+6(m-8)+(m-8)(m-1)<m^{2}-m-36.$

∎

######  Lemma 3.4.

Let $G\in\mathcal{G}_{m}^{2}$ with brace $\alpha_{2}(2,1,1,2,1)$. Then

$Mo_{e}(G)<\left\\{\begin{array}[]{ll}Mo_{e}(F_{1})=m^{2}-4m-9,&\hbox{if
$7\leq m\leq 16$};\\\ Mo_{e}(F_{1})=Mo_{e}(F_{2})=212,&\hbox{if $m=17$};\\\
Mo_{e}(F_{2})=m^{2}-3m-26,&\hbox{if $m\geq 18$}.\end{array}\right.$

###### Proof.

Suppose that $v_{i}$ $(i=1,...,5)$ be the vertices in $\alpha_{2}(2,1,1,2,1)$
of $G$, as shown in Fig. 4. Let $a_{i}$ be the number of pendent edges of
$v_{i}$ $(i=1,...,5)$. Suppose $a_{2}+a_{4}\geq a_{3}+a_{5}\geq 1$. For
$a_{1}<a_{2}+3a_{3}+a_{5}-3$, let $G_{1}$ be the graph obtained from $G$ by
shifting $a_{3}$ (resp. $a_{5}$) pendent edges from $v_{3}$ (resp. $v_{5}$) to
$v_{2}$ (resp. $v_{4}$). We deduce that

$\displaystyle Mo_{e}(G_{1})-Mo_{e}(G)=$
$\displaystyle(a_{2}+a_{3}+1-a_{1}-4)-(a_{1}+a_{3}+a_{5}+4-a_{2}-1)+(1+a_{2}+a_{3}-3-a_{4}-a_{5})$
$\displaystyle-$
$\displaystyle(a_{2}+1-a_{4}-a_{5}-3)+(a_{1}+3-a_{4}-a_{5}-2)-(a_{1}+a_{3}+3-a_{4}-2)$
$\displaystyle+$
$\displaystyle(a_{2}+a_{3}+a_{4}+a_{5}+3-3)-(a_{2}+a_{4}+3-a_{5}-a_{3}-3)+(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+4-1)$
$\displaystyle-$
$\displaystyle(a_{1}+a_{2}+a_{4}+4-a_{3}-1)+(a_{4}+a_{5}+3-1)-(a_{4}+a_{5}+3-1-a_{3})$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+3-2)-(a_{1}+a_{2}+a_{3}-a_{5}-2)$
$\displaystyle=$ $\displaystyle 2a_{2}+6a_{3}+2a_{5}-2a_{1}-6>0.$

Let $G_{2}$ be the graph obtained from $G_{1}$ by shifting $a_{4}$ pendent
edges from $v_{4}$ to $v_{1}$. We obtain

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{1}+a_{4}+4-a_{2}-1)-(a_{1}+4-a_{2}-1)+(a_{1}+a_{4}+3-2)-(a_{1}+3-a_{4}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{4}+3-2)-(a_{1}+a_{2}+3-2)+(a_{2}+1-3)-(a_{2}+1-3-a_{4})+(a_{2}+3-3)$
$\displaystyle-$ $\displaystyle(a_{2}+a_{4}+3-3)+(3-1)-(a_{4}+3-1)$
$\displaystyle=$ $\displaystyle 3a_{4}>0.$

Let $G_{3}$ be the graph obtained from $G_{2}$ by shifting $a_{2}$ pendent
edges from $v_{2}$ to $v_{1}$. We obtain

$\displaystyle Mo_{e}(G_{3})-Mo_{e}(G_{2})=$
$\displaystyle(a_{1}+a_{2}+4-1)-(a_{1}+4-a_{2}-1)+(a_{1}+a_{2}+3-2)-(a_{1}+3-2)+(1-3)$
$\displaystyle-$ $\displaystyle(a_{2}+1-3)+0-(a_{2}+3-3)$ $\displaystyle=$
$\displaystyle 2a_{2}>0.$

For $a_{1}>6-2a_{2}$, let $G_{4}$ be the graph obtained from $G_{3}$ by
shifting $a_{1}$ pendent edges from $v_{1}$ to $v_{2}$. We have

$\displaystyle Mo_{e}(G_{3})-Mo_{e}(G_{2})=$
$\displaystyle(a_{1}+a_{2}+1-4)-(a_{1}+4-a_{2}-1)+(3-2)-(a_{1}+3-2)+(a_{1}+a_{2}+1-3)$
$\displaystyle\qquad-$
$\displaystyle(a_{2}+1-3)+(a_{1}+a_{2}+3-3)-(a_{2}+3-3)$ $\displaystyle=$
$\displaystyle a_{1}+2a_{2}-6>0.$

Clearly, $G_{3}\cong F_{1}$ and $G_{4}\cong F_{2}$. By simple calculation, we
have $Mo_{e}(F_{1})=m^{2}-4m-9$, and $Mo_{e}(F_{2})=m^{2}-3m-26$. ∎

Figure 6:  The Graphs $F_{1},F_{2},F_{3},F_{4}$ of size $m$ in Lemmas 3.4, 3.5
and 3.6.

######  Lemma 3.5.

Let $G\in\mathcal{G}_{m}^{2}$ with brace $\alpha_{2}(2,1,1,2,2)$. Then
$Mo_{e}(G)<Mo_{e}(F_{3})=m^{2}-3m-20$.

###### Proof.

Suppose that $v_{i}$ $(i=1,...,6)$ be the vertices in $\alpha_{2}(2,1,1,2,2)$
of $G$, as shown in Fig. 4. Let $a_{i}$ be the number of pendent edges of
$v_{i}$ ($i=1,...,6$). For $a_{6}>0$, let $G_{1}$ be the graph obtained from
$G$ by shifting $a_{6}$ pendent edges from $v_{6}$ to $v_{1}$. We obtain

$\displaystyle Mo_{e}(G_{1})-Mo_{e}(G)=$
$\displaystyle(a_{1}+a_{3}+a_{5}+a_{6}+5-a_{2}-1)-(a_{1}+a_{3}+a_{5}+5-a_{2}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{4}+a_{6}+5-a_{3}-1)-(a_{1}+a_{2}+a_{4}+5-a_{3}-3)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{5}+a_{6}+4-a_{4}-2)-(a_{1}+a_{3}+a_{5}+4-a_{4}-a_{6}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{4}+a_{6}+4-a_{5}-2)-(a_{1}+a_{2}+a_{4}+4-a_{5}-a_{6}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{4}+a_{6}+4-a_{5}-2)-(a_{1}+a_{2}+a_{4}+4-a_{5}-a_{6}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{5}+4-a_{4}-2)-(a_{1}+a_{3}+a_{5}+4-a_{4}-a_{6}-2)$
$\displaystyle+$
$\displaystyle(a_{2}+1-a_{4}-3)-(a_{2}+1-a_{4}-a_{6}-3)+(a_{3}+1-a_{5}-3)-(a_{3}+1-a_{5}-a_{6}-3)$
$\displaystyle=$ $\displaystyle 11a_{6}>0.$

For $a_{2}+a_{3}>a_{1}$, let $G_{2}$ be the graph obtained from $G_{1}$ by
shifting $a_{3}$ (resp. $a_{5}$) pendent edges from $v_{3}$ (resp. $v_{5}$) to
$v_{2}$ (resp. $v_{4}$). We deduce that

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{2}+a_{3}+1-a_{1}-5)-(a_{1}+a_{3}+a_{5}+5-a_{2}-1)+(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+5-1)$
$\displaystyle-$
$\displaystyle(a_{1}+a_{2}+a_{4}+5-a_{3}-1)+(a_{1}+4-a_{4}-a_{5}-2)-(a_{1}+a_{3}+a_{5}+4-a_{4}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+4-2)-(a_{1}+a_{2}+a_{4}+4-a_{5}-2)+(a_{2}+a_{3}+1-a_{4}-a_{5}-3)$
$\displaystyle-$
$\displaystyle(a_{2}+1-a_{4}-3)+(3-1)-(a_{3}+1-a_{5}-3)+(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}-2)$
$\displaystyle-$
$\displaystyle(a_{1}+a_{2}+a_{4}+4-a_{5}-2)+(a_{1}+4-a_{4}-a_{5}-2)-(a_{1}+a_{3}+a_{5}+4-a_{4}-2)$
$\displaystyle=$ $\displaystyle 2a_{2}+2a_{3}-2a_{1}>0.$

For $a_{2}+a_{4}\geq 1$, let $G_{3}$ be the graph obtained from $G_{2}$ by
shifting $a_{2}$ (resp. $a_{4}$) pendent edges from $v_{2}$ (resp. $v_{4}$) to
$v_{1}$ (resp. $v_{4}$). We have

$\displaystyle Mo_{e}(G_{3})-Mo_{e}(G_{2})=$
$\displaystyle(a_{1}+a_{2}+a_{4}+5-1)-(a_{1}+5-a_{2}-1)+(a_{1}+a_{2}+a_{4}+5-1)-(a_{1}+5-a_{2}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{4}+4-2)-(a_{1}+a_{3}+a_{5}+4-a_{4}-2)+(1-3)-(a_{2}+1-a_{4}-3)$
$\displaystyle+$ $\displaystyle(a_{1}+a_{2}+a_{4}+4-2)-(a_{1}+4-a_{4}-2)$
$\displaystyle=$ $\displaystyle 5a_{2}+7a_{4}>0.$

Clearly, $G_{3}\cong F_{3}$, and $Mo_{e}(F_{3})=m^{2}-3m-20$. ∎

######  Lemma 3.6.

Let $G\in\mathcal{G}_{m}^{2}$ with brace $\alpha_{2}(3,1,1,2,1)$. Then
$Mo_{e}(G)<Mo_{e}(F_{4})=m^{2}-2m-33$.

###### Proof.

Suppose that $v_{i}$ $(i=1,...,6)$ be the vertices in $\alpha_{2}(3,1,1,2,1)$
of $G$, as shown in Fig. 4. Let $a_{i}$ be the number of pendent edges of
$v_{i}$ ($i=1,...,6$). For $a_{6}>0$, let $G_{1}$ be the graph obtained from
$G$ by shifting $a_{5}$ (resp. $a_{6}$) pendent edges from $v_{5}$ (resp.
$v_{6}$) to $v_{1}$. We obtain

$\displaystyle Mo_{e}(G_{1})-Mo_{e}(G)=$
$\displaystyle(a_{1}+a_{3}+a_{5}+a_{6}+3-a_{2}-2)-(a_{1}+a_{3}+a_{5}+3-a_{2}-a_{6}-2)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+5-1)-(a_{1}+a_{2}+a_{3}+a_{4}+5-a_{5}-a_{6}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+5-1)-(a_{1}+a_{2}+a_{3}+a_{4}+5-a_{5}-a_{6}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{5}+a_{6}+3-a_{2}-2)-(a_{1}+a_{3}+a_{5}+3-a_{2}-a_{6}-2)$
$\displaystyle+$
$\displaystyle(a_{2}+a_{4}+3-a_{3}-1)-(a_{2}+a_{4}+a_{6}+3-a_{3}-1)+(a_{3}+a_{4}+2-a_{2}-3)$
$\displaystyle-$
$\displaystyle(a_{2}+a_{6}+3-a_{3}-a_{4}-2)+(a_{1}+a_{5}+a_{6}+4-a_{2}-2)-(a_{1}+a_{5}+4-a_{4}-2)$
$\displaystyle=$ $\displaystyle 2a_{3}+4a_{5}+7a_{6}-2a_{2}-2>0.$

Let $G_{2}$ be the graph obtained from $G_{1}$ by shifting $a_{3}$ (resp.
$a_{4}$) pendent edges from $v_{3}$ (resp. $v_{4}$) to $v_{1}$ (resp.
$v_{2}$). We deduce that

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}+2-3)-(a_{1}+a_{3}+3-a_{2}-2)+(a_{1}+a_{2}+a_{3}+a_{4}+2-3)$
$\displaystyle-$
$\displaystyle(a_{1}+a_{3}+3-a_{2}-2)+(a_{1}+a_{2}+a_{3}+a_{4}+5-1)-(a_{1}+a_{2}+5-a_{3}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}+3-1)-(a_{2}+a_{4}+3-a_{3}-1)+(a_{1}+a_{2}+a_{3}+a_{4}+3-2)$
$\displaystyle-$ $\displaystyle(a_{2}+3-a_{3}-a_{4}-2)$ $\displaystyle=$
$\displaystyle a_{1}+3a_{2}+6a_{3}+5a_{4}>0.$

Let $G_{3}$ be the graph obtained from $G_{2}$ by shifting $a_{1}$ pendent
edges from $v_{1}$ to $v_{2}$. We obtain

$\displaystyle Mo_{e}(G_{3})-Mo_{e}(G_{2})=$
$\displaystyle(a_{1}+a_{2}+2-3)-(a_{1}+3-a_{2}-2)+(a_{1}+a_{2}+2-3)-(a_{2}+2-a_{1}-3)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+3-1)-(a_{2}+3-1)+(a_{1}+a_{2}+3-2)-(a_{2}+3-2)+(4-2)-(a_{1}+4-2)$
$\displaystyle=$ $\displaystyle 3a_{1}+2a_{2}-2>0.$

Thus, $Mo_{e}(G)<Mo_{e}(G_{1})<Mo_{e}(G_{2})<Mo_{e}(G_{3})$. Clearly,
$G_{3}\cong F_{4}$, and $Mo_{e}(F_{4})=m^{2}-2m-33$. ∎

######  Lemma 3.7.

Let $G\in\mathcal{G}_{m}^{2}$ of size $m$. Then $Mo_{e}(G)<m^{2}-m-36$ for
$m\geq 9$, and $Mo_{e}(G)\leq Mo_{e}(F_{1})$ for $m\leq 9$.

###### Proof.

Suppose that $G\in\mathcal{G}_{m}^{2}$, then $G$ has a brace
$\alpha_{2}(a_{1},a_{2},a_{3},a_{4},a_{5})$ as shown in Fig. 8. Assume that
$a_{4},a_{5}\geq 2$. We consider the following three possible cases.

Case 1. $a_{4},a_{5}\geq 3$.

Subcase 1.1. $a_{1}=a_{2}=a_{3}=1$.

We choose nine edges, three edges in the path $P(a_{4})$ such that two are
incident to $x$ or $y$ and one is in the middle of $P(a_{4})$, three edges in
the path $P(a_{5})$ such that two are incident to $x$ or $z$ and one is in the
middle of $P(a_{5})$, one edge in the path $P(a_{2})$ incident to $x$, one
edge in the path $P(a_{3})$ incident to $x$ and one edge in the path
$P(a_{1})$ incident to $y$. We have

$Mo_{e}(G)\leq 4(m-4)+4(m-7)+(m-9)+(m-9)(m-1)<m^{2}-m-36.$

Subcase 1.2. At least one of $a_{1},a_{2},a_{3}$ is greater than 1.

If $a_{2},a_{3}\geq 2$, then we choose 10 edges, three edges in the path
$P(a_{4})$ such that two are incident to $x$ or $y$ and one is in the middle
of $P(a_{4})$, three edges in the path $P(a_{5})$ such that two are incident
to $x$ or $z$ and one is in the middle of $P(a_{5})$, two edges in the path
$P(a_{2})$ incident to $x$ or $y$, one edge in the path $P(a_{3})$ incident to
$x$ and one edge in the path $P(a_{1})$ incident to $y$. We have

$Mo_{e}(G)\leq 2(m-4)+(m-5)+2(m-6)+2(m-8)+3(m-9)+(m-10)(m-1)<m^{2}-m-36.$

If $a_{1}\geq 2$, then we choose 10 edges, three edges in the path $P(a_{4})$
such that two are incident to $x$ or $y$ and one is in the middle of
$P(a_{4})$, three edges in the path $P(a_{5})$ such that two are incident to
$x$ or $z$ and one is in the middle of $P(a_{5})$, two edges in the path
$P(a_{2})$ incident to $x$ or $y$, one edge in the path $P(a_{3})$ incident to
$x$ and two edges in the path $P(a_{1})$ incident to $y$ or $z$. We obtain

$Mo_{e}(G)\leq 4(m-4)+6(m-7)+(m-10)(m-1)<m^{2}-m-36.$

Case 2. $a_{4}\geq 3,a_{5}=2$.

Subcase 2.1.$a_{4}\geq 4,a_{5}=2$, and $a_{1}=a_{2}=a_{3}=1$.

We choose nine edges, four edges in the path $P(a_{4})$ such that two are
incident to $x$ or $y$ and two are in the middle of $P(a_{4})$, two edges in
the path $P(a_{5})$ such that one is incident to $x$ and one is in the middle
of $P(a_{5})$, one edge in the path $P(a_{2})$ incident to $x$, one edge in
the path $P(a_{3})$ incident to $x$ and one edge in the path $P(a_{1})$
incident to $y$. We have

$Mo_{e}(G)\leq(m-4)+2(m-5)+(m-6)+2(m-7)+3(m-8)+(m-9)(m-1)<m^{2}-m-36.$

Subcase 2.2.$a_{4}=3,a_{5}=2$, and $a_{1}=a_{2}=a_{3}=1$.

The Subcase follows from Lemma 3.6.

Subcase 2.3.$a_{4}\geq 3,a_{5}=2$, and at least one of $a_{1},a_{2},a_{3}$ is
greater than 1.

The proof is similar to the Subcase 2.1.

Case 3. $a_{4}=a_{5}=2$.

Subcase 3.1. At least one of $a_{1},a_{2},a_{3}$ is greater than 1.

If $a_{2},a_{3}\geq 2$, then we choose eight edges, three edges in the path
$P(a_{4})$ such that two are incident to $x$ or $y$ and one is in the middle
of $P(a_{4})$, two edges in the path $P(a_{5})$ such that one is incident to
$x$ and other is in the middle of $P(a_{5})$, two edges in the path $P(a_{2})$
incident to $x$ or $y$, one edge in the path $P(a_{3})$ incident to $x$ and
one edge in the path $P(a_{1})$ incident to $y$. We have

$Mo_{e}(G)\leq 4(m-5)+4(m-7)+(m-8)(m-1)<m^{2}-m-36.$

If $a_{1}\geq 3$, then we choose nine edges, two edges in the path $P(a_{4})$
such that one is incident to $x$ and other is in the middle of $P(a_{4})$, two
edges in the path $P(a_{5})$ such that one is incident to $x$ and the other is
in the middle of $P(a_{5})$, one edge in the path $P(a_{2})$ incident to $x$,
one edge in the path $P(a_{3})$ incident to $x$ and three edges in the path
$P(a_{1})$ such that two are incident to $y$ or $z$ and one is in the middle
of $P(a_{1})$. We obtain

$Mo_{e}(G)\leq 2(m-5)+2(m-6)+4(m-7)+(m-9)+(m-9)(m-1)<m^{2}-m-36.$

If $a_{1}=2$, then by Lemma 3.5, $Mo_{e}(G)\leq m^{2}-3m-20<m^{2}-m-36.$

Subcase 3.2. $a_{1}=a_{2}=a_{3}=1$.

By Lemma 3.4, we have $Mo_{e}(G)<m^{2}-m-36$ for $m\geq 9$, and $Mo_{e}(G)\leq
Mo_{e}(F_{1})$ for $m\leq 9$. ∎

Figure 7:  The Graphs $H_{1},H_{2},H_{3},H_{4}$ of size $m$ in Lemmas 3.8, 3.9
and 3.10.

######  Lemma 3.8.

Let $G\in\mathcal{G}_{m}^{3}$ with brace $\alpha_{3}(1,2,2,2)$. Then

$Mo_{e}(G)<\left\\{\begin{array}[]{ll}Mo_{e}(H_{1})=m^{2}-4m-9,&\hbox{if
$7\leq m\leq 10$};\\\ Mo_{e}(H_{1})=Mo_{e}(H_{2})=68,&\hbox{if $m=11$};\\\
Mo_{e}(H_{2})=m^{2}-2m-31,&\hbox{if $m\geq 12$}.\end{array}\right.$

###### Proof.

Suppose that $v_{i}$ $(i=1,...,5)$ be the vertices in $\alpha_{3}(1,2,2,2)$ of
$G$ with $d_{G}(v_{1})=d_{G}(v_{2})=4$ and
$d_{G}(v_{3})=d_{G}(v_{4})=d_{G}(v_{5})=2$, as shown in Fig. 4. Let $a_{i}$ be
the number of pendent edges of $v_{i}$ $(i=1,...,5)$. Suppose that $a_{3}\geq
a_{4}\geq a_{5}$. For $a_{4}+a_{5}>a_{1}+a_{2}+8$, let $G_{1}$ be the graph
obtained from $G$ by shifting $a_{4}$ (resp. $a_{5}$) pendent edges from
$v_{4}$ (resp. $v_{5}$) to $v_{3}$. We deduce that

$\displaystyle Mo_{e}(G_{1})-Mo_{e}(G)=$
$\displaystyle(a_{3}+a_{4}+a_{5}+1-a_{1}-3)-(a_{1}+a_{4}+a_{5}+3-a_{3}-1)+(a_{3}+a_{4}+a_{5}+1-a_{2}-3)$
$\displaystyle-$
$\displaystyle(a_{1}+a_{4}+a_{5}+3-a_{3}-1)+(a_{1}+a_{3}+a_{4}+a_{5}+3-1)-(a_{1}+a_{3}+a_{5}+3-a_{4}-1)$
$\displaystyle+$
$\displaystyle(a_{2}+a_{3}+a_{4}+a_{5}+3-1)-(a_{2}+a_{3}+a_{5}+3-a_{4}-1)+(a_{1}+a_{3}+a_{4}+a_{5}+3-1)$
$\displaystyle-$
$\displaystyle(a_{1}+a_{3}+a_{4}+3-a_{5}-1)+(a_{1}+a_{3}+a_{4}+a_{5}+3-1)-(a_{2}+a_{3}+a_{4}+3-a_{5}-1)$
$\displaystyle=$ $\displaystyle 4(a_{3}+a_{4}+a_{5})-2(a_{1}+a_{2})-8>0.$

For $a_{2}+a_{3}>1$, let $G_{2}$ be the graph obtained from $G_{1}$ by
shifting $a_{2}$ ) pendent edges from $v_{2}$ to $v_{1}$. We have

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{1}+a_{2}+3-a_{3}-1)-(a_{1}+3-a_{3}-1)+(a_{3}+1-3)-(a_{2}+3-a_{3}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+3-3)-(a_{1}+3-a_{2}-3)+(a_{1}+a_{2}+a_{3}+3-1)-(a_{1}+a_{3}+3-1)$
$\displaystyle+$
$\displaystyle(a_{3}+3-1)-(a_{2}+a_{3}+3-1)+(a_{1}+a_{2}+a_{3}+3-1)-(a_{1}+a_{3}+3-1)$
$\displaystyle+$ $\displaystyle(a_{3}+3-1)-(a_{2}+a_{3}+3-1)$ $\displaystyle=$
$\displaystyle 2(a_{2}+a_{3})-4>0.$

Clearly, $G_{2}\cong H_{2}$ for $a_{1}=0,a_{3}>0$, and $G_{2}\cong H_{1}$ for
$a_{3}=0,a_{1}>0$. For $a_{1}+a_{3}>2$, let $G_{3}$ be the graph obtained from
$G_{2}$ by shifting $a_{1}$ pendent edges from $v_{1}$ to $v_{3}$. We have

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{1}+a_{3}+1-3)-(a_{1}+3-a_{3}-1)+(a_{1}+a_{3}+1-3)-(a_{3}+1-3)+(3-3)$
$\displaystyle-$
$\displaystyle(a_{1}+3-3)+(a_{1}+a_{3}+3-1)-(a_{3}+3-1)+(a_{1}+a_{3}+3-1)-(a_{3}+3-1)$
$\displaystyle=$ $\displaystyle 2(a_{1}+a_{3})-4>0.$

Thus, $Mo_{e}(G)<Mo_{e}(G_{1})<Mo_{e}(G_{2})<Mo_{e}(G_{3})$. Clearly,
$G_{3}\cong H_{2}$, and by simple calculation, we deduce that
$Mo_{e}(H_{2})=m^{2}-2m-31$, $Mo_{e}(H_{1})=m^{2}-4m-9$. ∎

######  Lemma 3.9.

Let $G\in\mathcal{G}_{m}^{3}$ with brace $\alpha_{3}(2,2,2,2)$. Then
$Mo_{e}(G)<Mo_{e}(H_{3})=m^{2}-m-48$.

###### Proof.

Suppose that $v_{i}$ $(i=1,...,6)$ be the six vertices in
$\alpha_{3}(2,2,2,2)$ of $G$ with $d_{G}(v_{1})=d_{G}(v_{2})=4$ and
$d_{G}(v_{3})=d_{G}(v_{4})=d_{G}(v_{5})=d_{G}(v_{6})=2$, as shown in Fig. 4.
Let $a_{i}$ be the number of pendent edges of $v_{i}$ $(i=1,...,6)$. Suppose
that $a_{3}\geq a_{4}\geq a_{5}\geq a_{6}>0$. Let $G_{1}$ be the graph
obtained from $G$ by shifting $a_{i}$ ( $i\geq 4$) pendent edges from $v_{i}$
( $i\geq 4$) to $v_{3}$. We obtain

$\displaystyle Mo_{e}(G_{1})-Mo_{e}(G)=$
$\displaystyle(a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+1-a_{1}-3)-(a_{1}+a_{4}+a_{5}+a_{6}+3-a_{2}-a_{3}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{4}+a_{5}+a_{6}+1-a_{2}-3)-(a_{2}+a_{4}+a_{5}+a_{6}+3-a_{1}-a_{3}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{4}+a_{5}+a_{6}+3-a_{2}-1)-(a_{1}+a_{3}+a_{5}+a_{6}+3-a_{4}-a_{2}-1)$
$\displaystyle+$
$\displaystyle(a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+3-a_{1}-1)-(a_{2}+a_{3}+a_{5}+a_{6}+3-a_{1}-a_{4}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{4}+a_{5}+a_{6}+3-a_{2}-1)-(a_{1}+a_{3}+a_{4}+a_{6}+3-a_{2}-a_{5}-1)$
$\displaystyle+$
$\displaystyle(a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+3-a_{1}-1)-(a_{2}+a_{3}+a_{4}+a_{6}+3-a_{1}-a_{5}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{4}+a_{5}+a_{6}+3-a_{2}-1)-(a_{1}+a_{3}+a_{4}+a_{5}+3-a_{2}-a_{6}-1)$
$\displaystyle+$
$\displaystyle(a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+3-a_{1}-1)-(a_{2}+a_{3}+a_{4}+a_{5}+3-a_{1}-a_{6}-1)$
$\displaystyle=$ $\displaystyle 4(a_{3}+a_{4}+a_{5}+a_{6})-8>0.$

For $a_{1}+a_{2}>0$, let $G_{2}$ be the graph obtained from $G_{1}$ by
shifting $a_{1}$ (resp. $a_{2}$) pendent edges from $v_{1}$ (resp. $v_{2}$) to
$v_{3}$. We have

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{1}+a_{2}+a_{3}+1-3)-(a_{2}+a_{3}+1-a_{1}-1)+(a_{1}+a_{2}+a_{3}+1-3)$
$\displaystyle-$
$\displaystyle(a_{2}+3-a_{1}-a_{3}-1)+(a_{1}+a_{2}+a_{3}+3-1)-(a_{1}+a_{3}+3-a_{2}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+3-1)-(a_{2}+a_{3}+3-a_{1}-1)+(a_{1}+a_{2}+a_{3}+3-1)$
$\displaystyle-$
$\displaystyle(a_{1}+a_{3}+3-a_{2}-1)+(a_{1}+a_{2}+a_{3}+3-1)-(a_{2}+a_{3}+3-a_{1}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+3-1)-(a_{1}+a_{3}+3-a_{2}-1)+(a_{1}+a_{2}+a_{3}+3-1)$
$\displaystyle-$ $\displaystyle(a_{2}+a_{3}+3-a_{1}-1)$ $\displaystyle=$
$\displaystyle 10a_{1}+6a_{2}+2a_{3}-8>0.$

Thus, $Mo_{e}(G)<Mo_{e}(G_{1})<Mo_{e}(G_{2})$. Clearly, $G_{2}\cong H_{3}$,
and by simple calculation, we obtain $Mo_{e}(H_{3})=m^{2}-m-48$. ∎

######  Lemma 3.10.

Let $G\in\mathcal{G}_{m}^{3}$ with brace $\alpha_{3}(1,2,2,3)$. Then
$Mo_{e}(G)<Mo_{e}(H_{4})=m^{2}-3m-24$.

###### Proof.

Suppose that $v_{i}$ $(i=1,...,6)$ be the six vertices in
$\alpha_{3}(1,2,2,3)$ of $G$ with $d_{G}(v_{1})=d_{G}(v_{2})=4$ and
$d_{G}(v_{3})=d_{G}(v_{4})=d_{G}(v_{5})=d_{G}(v_{6})=2$, as shown in Fig. 4.
Let $a_{i}$ be the number of pendent edges of $v_{i}$ $(i=1,...,6)$. Assume
that $a_{3}\geq a_{2}$, and $a_{4}+a_{5}+a_{6}>1$. Let $G_{1}$ be the graph
obtained from $G$ by shifting $a_{i}$ ( $i\geq 4$) pendent edges from $v_{i}$
( $i\geq 4$) to $v_{3}$. We get

$\displaystyle Mo_{e}(G_{1})-Mo_{e}(G)=$
$\displaystyle(a_{1}+4-a_{3}-a_{4}-a_{5}+-a_{6}-1)-(a_{1}+a_{4}+a_{5}+4-a_{3}-1)$
$\displaystyle+$
$\displaystyle(a_{3}+a_{4}+a_{5}+a_{6}+1-a_{2}-4)-(a_{2}+a_{4}+a_{6}+4-a_{3}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{3}+a_{4}+a_{5}+a_{6}+4-1)-(a_{1}+a_{3}+a_{5}+4-a_{4}-1)$
$\displaystyle+$
$\displaystyle(a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+4-1)-(a_{2}+a_{3}+a_{6}+4-a_{4}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+5-1)-(a_{1}+a_{2}+a_{2}+a_{4}+5-a_{5}-a_{6}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+5-1)-(a_{1}+a_{2}+a_{2}+a_{4}+5-a_{5}-a_{6}-1)$
$\displaystyle+$
$\displaystyle(a_{1}+3-a_{2}-3)-(a_{1}+a_{5}+3-a_{2}-a_{6}-3)+(a_{1}+3-a_{2}-3)$
$\displaystyle-$ $\displaystyle(a_{1}+a_{5}+3-a_{2}-a_{6}-3)$ $\displaystyle=$
$\displaystyle 2(a_{3}+a_{4}+a_{5})+6a_{6}-2a_{2}-12>0.$

For $a_{1}+a_{2}>0$, let $G_{2}$ be the graph obtained from $G_{1}$ by
shifting $a_{1}$ (resp. $a_{2}$) pendent edges from $v_{1}$ (resp. $v_{2}$) to
$v_{3}$. We have

$\displaystyle Mo_{e}(G_{2})-Mo_{e}(G_{1})=$
$\displaystyle(a_{1}+a_{2}+a_{3}+1-4)-(a_{3}+1-a_{1}-4)+(a_{1}+a_{2}+a_{3}+1-4)-(a_{3}+1-a_{2}-4)$
$\displaystyle\qquad+$
$\displaystyle(a_{1}+a_{2}+a_{3}+4-1)-(a_{1}+a_{3}+4-1)+(a_{1}+a_{2}+a_{3}+4-1)-(a_{2}+a_{3}+4-1)$
$\displaystyle\qquad+$
$\displaystyle(3-3)-(a_{1}+3-a_{2}-3)+(3-3)-(a_{1}+3-a_{2}-3)$
$\displaystyle=$ $\displaystyle 2a_{1}+6a_{2}>0.$

Thus, $Mo_{e}(G)<Mo_{e}(G_{1})<Mo_{e}(G_{2})$. Clearly, $G_{2}\cong H_{4}$,
and by simple calculation, we get $Mo_{e}(H_{4})=m^{2}-3m-248$. ∎

Figure 8:  The Graphs for Lemmas 3.3, 3.7, 3.11 and 3.12.

######  Lemma 3.11.

Let $G\in\mathcal{G}_{m}^{3}$ of size $m$. Then $Mo_{e}(G)<m^{2}-m-36$ for
$m\geq 9$, and $Mo_{e}(G)\leq Mo_{e}(H_{1})$ for $m\leq 9$.

###### Proof.

Suppose that $G\in\mathcal{G}_{m}^{3}$, then $G$ has a brace
$\alpha_{2}(a_{1},a_{2},a_{3},a_{4})$ as shown in Fig. 8. Assume that $1\leq
a_{1}\leq a_{2}\leq a_{3}\leq a_{4}$. We proceed with the following three
possible cases.

Case 1. $3\leq a_{1}\leq a_{2}\leq a_{3}\leq a_{4}$.

We choose twelve edges, eight edges in the paths $P(a_{i})$ $(i=1,2,3,4)$ such
that each one is incident to $x$ or $y$, four edges in the middle of
$P(a_{i})$ $(i=1,2,3,4)$. We deduce that

$Mo_{e}(G)\leq 8(m-8)+4(m-12)+(m-12)(m-1)<m^{2}-m-36.$

Case 2. $a_{1}=2$.

Subcase 2.1. $3\leq a_{2}\leq a_{3}\leq a_{4}$.

We choose eleven edges, eight edges in the paths $P(a_{i})$ $(i=1,2,3,4)$ such
that each one is incident to $x$ or $y$, three edges in the middle of
$P(a_{i})$ $(i=2,3,4)$. We deduce that

$Mo_{e}(G)\leq 6(m-7)+2(m-9)+3(m-11)+(m-11)(m-1)<m^{2}-m-36.$

Subcase 2.2. $a_{2}=a_{3}=a_{4}=2$.

The Subcase follows from Lemma 3.9.

Case 3. $a_{1}=1$.

Subcase 3.1. $3\leq a_{2}\leq a_{3}\leq a_{4}$.

We choose ten edges, six edges in the paths $P(a_{i})$ $(i=2,3,4)$ such that
each one is incident to $x$ or $y$, three edges in the middle of $P(a_{i})$
$(i=2,3,4)$, and one edge in $P(a_{1})$ incident to $x$. It follows that

$Mo_{e}(G)\leq 6(m-4)+4(m-10)+(m-10)(m-1)<m^{2}-m-36.$

Subcase 3.2. $a_{2}=2,3\leq a_{3}\leq a_{4}$.

The proof is similar to the Subcase 3.1.

Subcase 3.3. $a_{2}=a_{3}=2,3\leq a_{4}$.

If $a_{4}=3$, then it follows from Lemma 3.10. If $a_{4}\geq 4$, then we
choose nine edges, four edges in the path $P(a_{4})$ such that two are
incident to $x$ or $y$ and the other two are in the middle of $P(a_{4})$, two
edges in the path $P(a_{3})$ (resp. $P(a_{2})$) such that one is incident to
$x$ and the other is in the middle of $P(a_{3})$ (resp. $P(a_{2})$) and one
edge in $P(a_{1})$ incident to $x$. We have

$Mo_{e}(G)\leq 2(m-5)+2(m-7)+4(m-6)+(m-9)+(m-9)(m-1)<m^{2}-m-36.$

Subcase 3.4. $a_{2}=a_{3}=a_{4}=2$.

By Lemma 3.8, $Mo_{e}(G)<m^{2}-m-36$ for $m\geq 9$, and $Mo_{e}(G)\leq
Mo_{e}(H_{1})$ for $m\leq 9$. ∎

######  Lemma 3.12.

Let $G\in\mathcal{G}_{m}^{4}$ of size $m$. Then $Mo_{e}(G)<m^{2}-m-36$.

###### Proof.

Suppose that $G\in\mathcal{G}_{m}^{4}$, then $G$ has a brace
$\alpha_{4}(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6})$ as shown in Fig. 8. We
choose eight edges, two edges in the path $P(a_{5})$ such that each is
incident to $w$ or $y$, two edges in the path $P(a_{6})$ such that each is
incident to $z$ or $x$, the four edges $yz,yw,wx,zx$. We obtain

$Mo_{e}(G)\leq 4(m-5)+4(m-8)+(m-8)(m-1)<m^{2}-m-36.$

∎

The proof of the Theorem 1.1 follows from Lemmas 3.1, 3.3, 3.7, 3.11 and 3.12.

Acknowledgement: This work was supported by the National Natural Science
Foundation of China (Grant Nos. 12071194, 11571155 and 12071158).

## References

  * [1] M. Arockiaraj, J. Clement, N. Tratnik, Mostar indices of carbon nanostructures and circumscribed donut benzenoid systems, Int. J. Quantum Chem. 119 (2019), e26043.
  * [2] A. Ali, T. Došlić, Mostar index: results and perspectives, Appl. Math. Comput. 404 (2021), 126245.
  * [3] K. Deng, S. Li, On the extremal values for the Mostar index of trees with given degree sequence, Appl. Math. Comput. 390 (2021), 125598.
  * [4] K. Deng, S. Li, On the extremal Mostar indices of trees with a given segment sequence, Bull. Malays. Math. Sci. Soc. 45 (2021), 593–612.
  * [5] K. Deng, S. Li, Chemical trees with extremal Mostar index, MATCH Commun. Math. Comput. Chem. 85 (2021), 161–180.
  * [6] K. Deng, S. Li, Extremal catacondensed benzenoid with respect to the Mostar index, J. Math. Chem. 58 (2020), 1437–1465.
  * [7] T. Došlić, I. Martinjak, R. Škrekovski, S. T. Spužević, I. Zubac, Mostar index, J. Math. Chem. 56 (2018), 2995–3013.
  * [8] A. Ghalvandi, A. R. Ashrafi, M. H. Nezhaad, On Mostar and edge Mostar indices of graphs, J. Math. (2021), 6651220.
  * [9] N. Ghanbari, S. Alikhani, Mostar index and edge Mostar index of polymers, Comput. Appl. Math. 40 (2021), 260.
  * [10] O. C. Havare, Mostar index and edge Mostar index for some cycle related graphs, Rom. J. Math. Comput. Sci. 10 (2020), 53–66.
  * [11] F. Hayat, S.-J. Xu, Extremal results on the Mostar index of trees with parameters, Discrete Math. Algor. Appl. (2024), DOI: 10.1142/S1793830924500253.
  * [12] F. Hayat, S.-J. Xu, A lower bound on the Mostar index of tricyclic graphs, Filomat 39 (2024).
  * [13] F. Hayat, S.-J. Xu, B. Zhou, On bicyclic graphs with maximum edge Mostar index, (2023), arXiv.2306.02761.
  * [14] F. Hayat, B. Zhou, On cacti with large Mostar index, Filomat 33 (2019), 4865–4873.
  * [15] F. Hayat, B. Zhou, On Mostar index of trees with parameters, Filomat 33 (2019), 6453–6458.
  * [16] S. Huang, S. Li, M. Zhang, On the extremal Mostar indices of hexagonal chains, MATCH Commun. Math. Comput. Chem. 84 (2020), 249–271.
  * [17] M. Imran, S. Akhter, Z. Iqbal, Edge Mostar index of chemical structures and nanostructures using graph operations, Int. J. Quan. Chem. 120 (2020), e26259.
  * [18] G. Liu, K. Deng, The maximum Mostar indices of unicyclic graphs with given diameter, Appl. Math. Comput. 439 (2023), 127636.
  * [19] H. Liu, L. Song, Q. Xiao, Z. Tang, On edge Mostar index of graphs, Iranian J. Math. Chem. 11 (2020), 95–106.
  * [20] A. Tepeh, Extremal bicyclic graphs with respect to Mostar index, Appl. Math. Comput. 355 (2019), 319–324.
  * [21] Q. Xiao, M. Zeng, Z. Tang, The hexagonal chains with the first three maximal Mostar indices, Discrete Appl. Math. 288 (2020), 180–191.
  * [22] Q. Xiao, M. Zeng, Z. Tang, H. Deng, H. Hua, Hexagonal chains with first three minimal Mostar indices, MATCH Commun. Math. Comput. Chem. 85 (2021), 47–61.