# On Jensen Functional, Convexity and Uniform Convexity

Shoshana Abramovich  Department of Mathematics, University of Haifa, Haifa,
Israel<EMAIL_ADDRESS>
(Date: May 22, 2024)

###### Abstract.

In this paper we improve results related to Normalized Jensen Functional for
convex functions and Uniformly Convex Functions.

###### Key words and phrases:

Jensen Functionals, Convexity, Uniform Convexity

###### 1991 Mathematics Subject Classification:

26D15, 26A51, 39B62, 47A63, 47A64

##  1\.
Introduction

In this paper we extend and refine Jensen Functional type inequalities that
appeared in [3], [5] and [4]. Jensen functional is:

$J_{n}\left(f,\mathbf{x},\mathbf{p}\right)=\sum_{i=1}^{n}p_{i}f\left(x_{i}\right)-f\left(\sum_{i=1}^{n}p_{i}x_{i}\right).$

We start with some theorems, definitions and notations that appeared in these
papers and are used here.

######  Theorem 1.

[5] Consider the normalized Jensen functional where
$f:C\longrightarrow\mathbb{R}$ is a convex function on the convex set $C$ in a
real linear space, $\mathbf{x}=\left(x_{1},...,x_{n}\right)\in C^{n},$ and
$\mathbf{p}=\left(p_{1},...,p_{n}\right),$
$\mathbf{q}=\left(q_{1},...,q_{n}\right)$ are non-negative n-tuples satisfying
$\sum_{i=1}^{n}p_{i}=1,$ $\sum_{i=1}^{n}q_{i}=1,$ $q_{i}>0,$ $i=1,...,n$. Then

(1.1) $MJ_{n}\left(f,\mathbf{x},\mathbf{q}\right)\geq
J_{n}\left(f,\mathbf{x},\mathbf{p}\right)\geq
mJ_{n}\left(f,\mathbf{x},\mathbf{q}\right),\qquad$

provided that

$m=\min_{1\leq i\leq n}\left(\frac{p_{i}}{q_{i}}\right),\quad M=\max_{1\leq
i\leq n}\left(\frac{p_{i}}{q_{i}}\right).$

In, Section 2 we use Theorem 2 and the following notations:

Let
$\mathbf{x}_{\uparrow}=\left(x_{\left(1\right)},...,x_{\left(n\right)}\right)$
be the increasing rearrangement of $\mathbf{x=}\left(x_{1},...,x_{n}\right).$
Let $\pi$ be the permutation that transfers $\mathbf{x}$ into
$\mathbf{x}_{\uparrow}$ and let
$\left(\overline{p}_{1},...,\overline{p}_{n}\right)$ and
$\left(\overline{q}_{1},...,\overline{q}_{n}\right)$ be the $n$-tuples
obtained by the same permutation $\pi$ on $\left(p_{1},...,p_{n}\right)$ and
$\left(q_{1},...,q_{n}\right)$ respectively. Then for an $n$-tuple
$\mathbf{x}=\left(x_{1},...,x_{n}\right),$ $x_{i}\in I$ , $i=1,...,n$ where
$I$ is an interval in $\mathbb{R}$ we get the following results:

######  Theorem 2.

[3, Theorem 4] Let $\mathbf{p}=\left(p_{1},...,p_{n}\right),$ where $\
0\leq\sum_{j=1}^{i}\overline{p}_{j}\leq 1,$ $i=1,...,n,$
$\sum_{i=1}^{n}p_{i}=1,$ and $\mathbf{q}=\left(q_{1},...,q_{n}\right),$
$0<\sum_{j=1}^{i}\overline{q}_{j}<1,$ $i=1,...,n-1$, $\sum_{i=1}^{n}q_{i}=1,$
and $\ \mathbf{p}\neq$ $\mathbf{q}.$ Denote

$m_{i}:=\frac{\sum_{j=1}^{i}\overline{p}_{j}}{\sum_{j=1}^{i}\overline{q}_{j}},\qquad\overline{m}_{i}=:\frac{\sum_{j=i}^{n}\overline{p}_{j}}{\sum_{j=i}^{n}\overline{q}_{j}},\qquad
i=1,...,n$

where $\left(\overline{p}_{1},...,\overline{p}_{n}\right)$ and
$\left(\overline{q}_{1},...,\overline{q}_{n}\right)$ are as denoted above, and

$m^{\ast}:=\min_{1\leq i\leq n}\left\\{m_{i},\overline{m_{i}}\right\\},\qquad
M^{\ast}:=\max_{1\leq i\leq n}\left\\{m_{i},\overline{m_{i}}\right\\}.$

If $\mathbf{x}=\left(x_{1},...,x_{n}\right)$ is any n-tuple in $I^{n},$ where
$I$ is an interval in $\mathbb{R},$ then

(1.2) $M^{\ast}J_{n}\left(f,\mathbf{x},\mathbf{q}\right)\geq
J_{n}\left(f,\mathbf{x},\mathbf{p}\right)\geq
m^{\ast}J_{n}\left(f,\mathbf{x},\mathbf{q}\right),$

where $f:I\longrightarrow\mathbb{R}$ is a convex function on the interval $I$.

######  Remark 1.

[3, Remark 3] If $\underset{1\leq i\leq
n}{min}\left(\frac{p_{i}}{q_{i}}\right)=\frac{\overline{p}_{k}}{\overline{q}_{k}},$
$k\neq 1,n$ or $\underset{1\leq i\leq
n}{\max}\left(\frac{p_{i}}{q_{i}}\right)=\frac{\overline{p}_{s}}{\overline{q}_{s}},$
$\ s\neq 1,n$ then it is clear that for $p_{i}\geq 0,$ and $q_{i}>0,$ we get
that$\ \ m^{\ast}>m$ and $M^{\ast}<M$ and in these cases (1.2) refines (1.1).

In Section 3 we deal with refinements of Theorem 1 through Uniform Convexity.

######  Definition 1.

[1] Let $I=\left[a,b\right]\subset\mathbb{R}$ be an interval and
$\Phi:\left[0,b-a\right]\rightarrow\mathbb{R}$ be a function. A function
$f:\left[a,b\right]\rightarrow\mathbb{R}$ is said to be generalized
$\Phi$-uniformly convex if:

$\displaystyle tf\left(x\right)+\left(1-t\right)f\left(y\right)$
$\displaystyle\geq$ $\displaystyle
f\left(tx+\left(1-t\right)y\right)+t\left(1-t\right)\Phi\left(\left|x-y\right|\right)$
$\displaystyle\text{for \ }x,y$ $\displaystyle\in$ $\displaystyle I\text{ \
and }t\in\left[0,1\right]\text{.}$

If in addition $\Phi\geq 0$, then $f$ is said to be $\Phi$-uniformly convex.

######  Remark 2.

It is proved in [9] that when $f$ is $\Phi$-uniformly convex, there is always
a modulus $\Phi$ which is increasing and $\Phi\left(0\right)=0$. We use this
type of $\Phi$ from Theorem 8 on.

In Theorem 3, the moduli $\Phi\ $are used as in Remark 2:

######  Theorem 3.

[7, Theorem 2.3] Let $f:\left[a,b\right]\rightarrow\mathbb{R}$ be an uniformly
convex function with modulus
$\Phi:\left[0,b-a\right]\rightarrow\mathbb{R}_{+},$
$\left\\{x_{k}\right\\}_{k=1}^{n}\subseteq\left[a,b\right]$ be a sequence and
let $\pi$ be a permutation on $\left\\{1,...,n\right\\}$ such that
$x_{\pi\left(1\right)}\leq x_{\pi\left(2\right)}\leq...\leq
x_{\pi\left(n\right)}$. Then the inequality

(1.3)
$\sum_{k=1}^{n}p_{k}f\left(x_{k}\right)-f\left(\sum_{k=1}^{n}p_{k}x_{k}\right)\geq\sum_{k=1}^{n-1}p_{\pi\left(k\right)}p_{\pi\left(k+1\right)}\Phi\left(x_{\pi\left(k+1\right)}-x_{\pi\left(k\right)}\right),$

holds for every convex combination $\sum_{k=0}^{n}p_{k}x_{k}$ of points
$x_{k}\in\left[a,b\right]$.

For $f=\Phi=x^{2},$ $x\geq 0$, we get for $n=2$, that there is an equality in
(1.3) and for $n\geq 3,$ $f=\Phi=x^{2},$ $x\geq 0$ (1.3) is mostly a strict
inequality

##  2\. Improved Jensen functional through Theorem 2

In this section we assume that $x_{i}\leq x_{i+1}$, $i=1,...,n-1$. Theorems 4,
5 and 6 are easily proved by Theorem 2. Theorems 4, and 6 refine results in
[6].

######  Theorem 4.

Let $f$ be a convex function on $I$ and
$\mathbf{x\in}\left[a,b\right]^{n}\subset I^{n}$. Let
$\mathbf{p}=\left(p_{1},...,p_{n}\right),$ where $\
0\leq\sum_{j=1}^{i}p_{j}\leq 1,$ $i=1,...,n,$ $\sum_{i=1}^{n}p_{i}=1,$then,

(2.1)
$0\leq\sum_{i=1}^{n}p_{i}f\left(x_{i}\right)-f\left(\sum_{i=1}^{n}p_{i}x_{i}\right)\leq
M^{\ast}\left(\frac{f\left(a\right)+f\left(b\right)}{2}-f\left(\frac{a+b}{2}\right)\right).$

If in addition $p_{i}\geq 0$, $i=1,...,n$ then

$\displaystyle 0$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n}p_{i}f\left(x_{i}\right)-f\left(\sum_{i=1}^{n}p_{i}x_{i}\right)\leq
M^{\ast}\left(\frac{f\left(a\right)+f\left(b\right)}{2}-f\left(\frac{a+b}{2}\right)\right)$
$\displaystyle<$ $\displaystyle
2\left(\frac{f\left(a\right)+f\left(b\right)}{2}-f\left(\frac{a+b}{2}\right)\right),$

where $M^{\ast}$ is as defined in Theorem 2 when $q_{0}=q_{n+1}=\frac{1}{2}$,
$p_{0}=p_{n+1}=0$, $q_{i}=0$,$\ i=1,...,n$.

###### Proof.

As we emphasized in the beginning of this section, we assume without loss of
generality that $x_{i}\leq x_{i+1}$, $i=1,...,n-1$. Choosing $p_{0}=p_{n+1}=0$
and $q_{0}=\frac{1}{2}=q_{n+1}$, $q_{i}=0,$ $i=1,...,n$, and also $x_{0}=a$,
$\ x_{n+1}=b$, then according to Theorem 2 for $n+2$ terms we get that (2.1)
holds.

If in addition $p_{i}\geq 0$, $i=1,...,n$, then $M^{\ast}<2$ according to
Remark 1, therefore (4) holds. ∎

Theorem 4 refines [6, Theorem 2.2] where it is proved that
$0\leq\sum_{i=1}^{n}p_{i}f\left(x_{i}\right)-f\left(\sum_{i=1}^{n}p_{i}x_{i}\right)\leq
2\left(\frac{f\left(a\right)+f\left(b\right)}{2}-f\left(\frac{a+b}{2}\right)\right)$.

In Section 3, we refine (5) in Theorem 5 for $\Phi$-uniformly convex functions
$f$.

######  Theorem 5.

[6, Theorem 2.3] Let $f$ be a convex function on $I=\left[a,b\right]$ and
$p,q>0,$ $p+q=1$. Then,

$\displaystyle\min\left\\{p,q\right\\}\left[f\left(a\right)+f\left(b\right)-2f\left(\frac{a+b}{2}\right)\right]$
$\displaystyle\leq$ $\displaystyle
pf\left(a\right)+qf\left(b\right)-f\left(pa+qb\right)$ $\displaystyle\leq$
$\displaystyle\max\left\\{p,q\right\\}\left[f\left(a\right)+f\left(b\right)-2f\left(\frac{a+b}{2}\right)\right]$

###### Proof.

Inequality (5) is a particular case of Theorem 1. ∎

######  Theorem 6.

Let $f$ be a convex function on $I$ and
$\mathbf{x\in}\left[a,b\right]^{n}\subset I^{n}$. Let
$\mathbf{p}=\left(p_{1},...,p_{n}\right),$ where $\
0\leq\sum_{j=1}^{i}p_{j}\leq 1,$ $i=1,...,n,$ $\sum_{i=1}^{n}p_{i}=1$, and let
$m^{\ast}$ and $M^{\ast}$ as in Theorem 2 when $q_{i}=\frac{1}{n},$
$i=1,...,n$. Then,

$\displaystyle
m^{\ast}\left[\sum_{i=1}^{n}\frac{f\left(x_{i}\right)}{n}-f\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right]$
$\displaystyle\leq$ $\displaystyle J_{n}\left(f,\mathbf{x,p}\right)$
$\displaystyle\leq$ $\displaystyle
M^{\ast}\left[\sum_{i=1}^{n}\frac{f\left(x_{i}\right)}{n}-f\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right].$

If $p_{i}\geq 0$, $i=1,...,n$ then

$\displaystyle\underset{1\leq i\leq
n}{\min}\left\\{p_{i}\right\\}\left[\sum_{i=1}^{n}f\left(x_{i}\right)-nf\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right]$
$\displaystyle\leq$ $\displaystyle
m^{\ast}\left[\sum_{i=1}^{n}\frac{f\left(x_{i}\right)}{n}-f\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right]$
$\displaystyle\leq$ $\displaystyle J_{n}\left(f,\mathbf{x,p}\right)$
$\displaystyle\leq$ $\displaystyle
M^{\ast}\left[\sum_{i=1}^{n}\frac{f\left(x_{i}\right)}{n}-f\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right]$
$\displaystyle\leq$ $\displaystyle\underset{1\leq i\leq
n}{\max}\left\\{p_{i}\right\\}\left[\sum_{i=1}^{n}f\left(x_{i}\right)-nf\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right].$

###### Proof.

As emphasized in the beginning of this section, we may assume, without loss of
generality, that $x_{i}\leq x_{i+1}$, $i=1,...,n-1.$ Using Theorem 2 when
$q_{i}=\frac{1}{n}$, $i=1,...,n$ we get that (6) holds.

If $p_{i}\geq 0,$ $i=1,...,n$ then according to Remark 1
$M^{\ast}<\underset{1\leq i\leq
n}{\max}\left(\frac{p_{i}}{\left(\frac{1}{n}\right)}\right)$, unless
$M^{\ast}=\underset{1\leq i\leq
n}{\max}\left(\frac{p_{i}}{\left(\frac{1}{n}\right)}\right)=\frac{p_{1}}{\left(\frac{1}{n}\right)}$,
or $M^{\ast}=\underset{1\leq i\leq
n}{\max}\left(\frac{p_{i}}{\left(\frac{1}{n}\right)}\right)=\frac{p_{n}}{\left(\frac{1}{n}\right)}$
and $m^{\ast}>\underset{1\leq i\leq
n}{\min}\left(\frac{p_{i}}{\left(\frac{1}{n}\right)}\right)$ unless
$m^{\ast}=\underset{1\leq i\leq
n}{\min}\left(\frac{p_{i}}{\left(\frac{1}{n}\right)}\right)=\frac{p_{1}}{\left(\frac{1}{n}\right)}$,
or $m^{\ast}=\underset{1\leq i\leq
n}{\min}\left(\frac{p_{i}}{\left(\frac{1}{n}\right)}\right)=\frac{p_{n}}{\left(\frac{1}{n}\right)}$
. Hence (6) holds. ∎

Theorem 6 refines [6, Theorem 2.4] where it is proved that when $p_{i}\geq 0$,
$i=1,...,n$,

$\displaystyle\underset{1\leq i\leq
n}{\min}\left\\{p_{i}\right\\}\left[\sum_{i=1}^{n}f\left(x_{i}\right)-nf\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right]$
$\displaystyle\leq$ $\displaystyle
J_{n}\left(f,\mathbf{x,p}\right)\leq\underset{1\leq i\leq
n}{\max}\left\\{p_{i}\right\\}\left[\sum_{i=1}^{n}f\left(x_{i}\right)-nf\left(\frac{\sum_{i=1}^{n}x_{i}}{n}\right)\right]$

holds.

##  3\.  Improved Jensen functional through $\Phi$-uniform convexity

From here on we deal with results related to $\Phi$-uniformly convex functions
which refine Theorem 1 and Theorem 5.

We start this section discussing two inequalities, the first is proved by
using the basic properties of uniformly convex functions as proved in [9], [8,
Theorem 1] and [2]. The other inequality about uniformly convexity is derived
from results in [7].

######  Remark 3.

In [9, Theorem 2.1], [8, Theorem 1, Inequality (23)] and [2, Inequality 8], it
is proved that the set of $\Phi$-uniformly convex functions $f$ which are
continuously differentiable satisfy the inequality

(3.1) $f\left(y\right)-f\left(x\right)\geq
f^{{}^{\prime}}\left(x\right)\left(y-x\right)+\Phi\left(\left|y-x\right|\right)$

and therefore, from (3.1) also the inequality

(3.2)
$\sum_{i=1}^{n}p_{i}f\left(x_{i}\right)-f\left(\sum_{i=1}^{n}p_{i}x_{i}\right)\geq\sum_{i=1}^{n}p_{i}\Phi\left(\left|x_{i}-\sum_{j=1}^{n}p_{j}x_{j}\right|\right).$

From (3.2) in Remark 3 we get refinements of Theorem 1 and Theorem 5.

######  Theorem 7.

Under the same conditions and definitions on $\ \mathbf{p},$ $\mathbf{q},$
$\mathbf{x},$ $m$ and $M$ as in Theorem 1, if
$f:\left[0,b\right)\rightarrow\mathbb{R},$ $0<b\leq\infty,$ is contineously
differential and is a $\Phi$-Uniformly Convex function,
$\sum_{j=1}^{n}p_{j}x_{j}=\overline{x}_{p}$ and
$\sum_{j=1}^{n}q_{j}x_{j}=\overline{x}_{q}$,
$\mathbf{x}\in\left[0,b\right)^{n},$ then the following inequlities hold:

(3.3)
$J_{n}\left(f,\mathbf{x},\mathbf{p}\right)-mJ_{n}\left(f,\mathbf{x},\mathbf{q}\right)\geq
m\Phi\left(\left|\overline{x}_{q}-\overline{x}_{p}\right|\right)+\sum_{i=1}^{n}\left(p_{i}-mq_{i}\right)\Phi\left(\left|x_{i}-\overline{x}_{p}\right|\right),$

and

(3.4)
$MJ_{n}\left(f,\mathbf{x},\mathbf{q}\right)-J_{n}\left(f,\mathbf{x},\mathbf{p}\right)\geq\sum_{i=1}^{n}\left(Mq_{i}-p_{i}\right)\Phi\left(\left|x_{i}-\overline{x}_{q}\right|\right)+\Phi\left(\left|\overline{x}_{q}-\overline{x}_{p}\right|\right)$

In the special case that $n=2$ and $m=\frac{p_{1}}{q_{1}}$ we get the
inequality

$\displaystyle
J_{2}\left(f,\mathbf{x},\mathbf{p}\right)-\frac{p_{1}}{q_{1}}J_{2}\left(f,\mathbf{x},\mathbf{q}\right)$
$\displaystyle\geq$
$\displaystyle\frac{p_{1}}{q_{1}}\Phi\left(\left|\overline{x}_{q}-\overline{x}_{p}\right|\right)+\left(p_{2}-\frac{p_{1}}{q_{1}}q_{2}\right)\Phi\left(p_{1}\left|x_{2}-x_{1}\right|\right)$
$\displaystyle=$ $\displaystyle
m\Phi\left(\left|\overline{x}_{q}-\overline{x}_{p}\right|\right)+\left(1-m\right)\Phi\left(p_{1}\left|x_{2}-x_{1}\right|\right),$

and

$\displaystyle\frac{p_{2}}{q_{2}}J_{2}\left(f,\mathbf{x},\mathbf{q}\right)-J_{2}\left(f,\mathbf{x},\mathbf{p}\right)$
$\displaystyle\geq$
$\displaystyle\left(\frac{p_{2}}{q_{2}}q_{1}-p_{1}\right)\Phi\left(\left|q_{2}\left(x_{2}-x_{1}\right)\right|\right)+\Phi\left(\left|\overline{x}_{q}-\overline{x}_{p}\right|\right).$

When $q_{1}=q_{2}=\frac{1}{2}$ we get from (7) and (7) the inequalities that
refine Theorem 5:

$\displaystyle
J_{2}\left(f,\mathbf{x},\mathbf{p}\right)-2p_{1}\left(\frac{f\left(x_{1}\right)+f\left(x_{2}\right)}{2}-f\left(\frac{x_{1}+x_{2}}{2}\right)\right)$
$\displaystyle\geq$ $\displaystyle
2p_{1}\Phi\left(\left|\frac{x_{1}+x_{2}}{2}-\overline{x}_{p}\right|\right)+\left(1-2p_{1}\right)\Phi\left(p_{1}\left|x_{2}-x_{1}\right|\right)$

and

$\displaystyle\frac{p_{2}}{q_{2}}\left(\frac{f\left(x_{1}\right)+f\left(x_{2}\right)}{2}-f\left(\frac{x_{1}+x_{2}}{2}\right)\right)-J_{2}\left(f,\mathbf{x},\mathbf{p}\right)$
$\displaystyle\geq$
$\displaystyle\left(p_{2}-p_{1}\right)\Phi\left(\left|\left(\frac{x_{2}-x_{1}}{2}\right)\right|\right)+\Phi\left(\left|\frac{x_{1}+x_{2}}{2}-\overline{x}_{p}\right|\right).$

In the special case that $f\left(x\right)=\Phi\left(x\right)=x^{2},$ $x\geq 0$
we get equalities in (3.3), (3.4), (7), (7), (7) and (7).

###### Proof.

To prove (3.3) we define $\mathbf{y}$ as

$y_{i}=\left\\{\begin{array}[]{ll}x_{i},&i=1,...,n\\\
\sum_{j=1}^{n}q_{j}x_{j},&i=n+1\end{array}\right.,$

and $\mathbf{d}$ as

$d_{i}=\left\\{\begin{array}[]{ll}p_{i}-mq_{i},&i=1,...,n\\\
m,&i=n+1\end{array}\right..$

Then (3.2) for $\mathbf{y}$ and $\mathbf{d}$ is

$\displaystyle\sum_{i=1}^{n}\left(p_{i}-mq_{i}\right)f\left(x_{i}\right)+mf\left(\sum_{i=1}^{n}q_{i}x_{i}\right)-f\left(\sum_{i=1}^{n}p_{i}x_{i}\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n+1}d_{i}f\left(y_{i}\right)-f\left(\sum_{i=1}^{n+1}d_{i}y_{i}\right)\geq\sum_{i=1}^{n+1}d_{i}\Phi\left(\left|y_{i}-\sum_{j=1}^{n+1}d_{j}y_{j}\right|\right)$
$=\sum_{i=1}^{n}\left(p_{i}-mq_{i}\right)\Phi\left(\left|x_{i}-\sum_{j=1}^{n}p_{j}x_{j}\right|\right)+m\Phi\left(\left|\sum_{i=1}^{n}\left(p_{i}-q_{i}\right)x_{i}\right|\right)$

which is (3.3) and therefore also (7) and (7) are satisfied.

To get (3.4), we choose $\mathbf{z}$ and $\mathbf{r}$ as

$z_{i}=\left\\{\begin{array}[]{ll}x_{i},&i=1,...,n\\\
\sum_{j=1}^{n}p_{j}x_{j},&i=n+1\end{array}\right.,$

and

$r_{i}=\left\\{\begin{array}[]{ll}q_{i}-\frac{p_{i}}{M},&i=1,...,n\\\
\frac{1}{M},&i=n+1\end{array}\right..$

Then, as $f$ is $\Phi$-uniformly convex, $\sum_{i=1}^{n+1}r_{i}=1,$ $r_{i}\geq
0,$ and $\sum_{i=1}^{n}q_{i}x_{i}=\sum_{i=1}^{n+1}r_{i}z_{i}$, we get that

$\displaystyle\sum_{i=1}^{n}\left(q_{i}-\frac{p_{i}}{M}\right)f\left(x_{i}\right)+\frac{1}{M}f\left(\sum_{i=1}^{n}p_{i}x_{i}\right)-f\left(\sum_{i=1}^{n}q_{i}x_{i}\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n+1}r_{i}f\left(z_{i}\right)-f\left(\sum_{i=1}^{n+1}r_{i}z_{i}\right)$
$\displaystyle\geq$
$\displaystyle\sum_{i=1}^{n+1}r_{i}\Phi\left(\left|z_{i}-\sum_{i=1}^{n+1}r_{i}z_{i}\right|\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n}\left(q_{i}-\frac{p_{i}}{M}\right)\Phi\left(\left|x_{i}-\sum_{j=1}^{n}q_{j}x_{j}\right|\right)+\frac{1}{M}\Phi\left(\left|\sum_{i=1}^{n}\left(p_{i}-q_{i}\right)x_{i}\right|\right)$

which is equivalent to (3.4), and therefore also (7) and (7) are satisfied.
The proof of the theorem is complete. ∎

The proof of Theorem 7 is similar to the proof of [3, Theorem 3], there it is
about superquadratic functions.

In Theorem 7 we used (3.2) to prove a refinement of Theorem 1 through
$\Phi$-uniformly convex functions.

From Theorem 3 we get another refinement of Theorem 1 and Theorem 5 proved in
the following theorem where $\Phi$ satisfies the conditions of Remark 2:

######  Theorem 8.

Under the same conditions and definitions on $\ \mathbf{p},$ $\mathbf{q},$
$\mathbf{x},$ $m$ as in Theorem 1, if
$f:\left[a,b\right)\rightarrow\mathbb{R},$ is a $\Phi$-Uniformly Convex
function, where $\Phi:\left[0,b-a\right)\rightarrow\mathbb{R}_{+},$
$\sum_{j=1}^{n}p_{j}x_{j}=\overline{x}_{p}$ and
$\sum_{j=1}^{n}q_{j}x_{j}=\overline{x}_{q}$,
$\mathbf{x}\in\left[0,b\right)^{n}$ and also $x_{1}\leq x_{2}\leq,...,\leq
x_{k-1}\leq\sum_{i=1}^{n}q_{i}x_{i}\leq x_{k}\leq x_{k+1}\leq,...,\leq x_{n}$,
then the following inequlity holds:

$\displaystyle
J_{n}\left(f,\mathbf{x},\mathbf{p}\right)-mJ_{n}\left(f,\mathbf{x},\mathbf{q}\right)$
$\displaystyle\geq$ $\displaystyle\sum_{i=1,i\neq
k-1}^{n}\left(p_{i}-mq_{i}\right)\left(p_{i+1}-mq_{i+1}\right)\Phi\left(x_{i+1}-x_{i}\right)$
$\displaystyle+m\left(p_{k-1}-mq_{k-1}\right)\Phi\left(\sum_{i=1}^{n}q_{i}x_{i}-x_{k-1}\right)+m\left(p_{k}-mq_{k}\right)\Phi\left(x_{k}-\sum_{i=1}^{n}q_{i}x_{i}\right).$

###### Proof.

It is given here that the sequence $\mathbf{x}\ $is increasing. Therefore we
can apply the inequality (1.3) in Theorem 3 for the also increasing
$(n+1)$-tuple $\mathbf{y=}\left(y_{1},...,y_{n+1}\right)$

(3.10) $y_{i}=\left\\{\begin{array}[]{ll}x_{i,}&i=1,...,k-1\\\
\sum_{j=1}^{n}q_{j}x_{j},&i=k\\\ x_{i-1},&i=k+1,...,n+1\end{array}\right.$

and to

(3.11) $d_{i}=\left\\{\begin{array}[]{ll}p_{i}-mq_{i},&i=1,...,k-1\\\
m,&i=k\\\ p_{i-1}-mq_{i-1},&i=k+1,...,n+1\end{array}\right.,$

where $m=\underset{1\leq i\leq n}{\min}\left(\frac{p_{i}}{q_{i}}\right)$, and
we get from Theorem 3 that

$\displaystyle
J_{n}\left(f,\mathbf{x},\mathbf{p}\right)-mJ_{n}\left(f,\mathbf{x},\mathbf{q}\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n+1}d_{i}f\left(y_{i}\right)-f\left(\sum_{i=1}^{n+1}d_{i}y_{i}\right)\geq\sum_{i=1}^{n+1}d_{i}d_{i+1}\Phi\left(\left|y_{i+1}-y_{i}\right|\right).$

This inequality means by (3.10) and (3.11) that

$\displaystyle\sum_{i=1}^{k-1}\left(p_{i}-mq_{i}\right)f\left(x_{i}\right)+mf\left(\sum_{i=1}^{n}p_{i}x_{i}\right)+\sum_{i=k}^{n}\left(p_{i}-mq_{i}\right)f\left(x_{i}\right)$
$\displaystyle\geq$ $\displaystyle\sum_{i=1,i\neq
k-1}^{n}\left(p_{i}-mq_{i}\right)\left(p_{i+1}-mq_{i+1}\right)\Phi\left(x_{i+1}-x_{i}\right)$
$\displaystyle+m\left(p_{k-1}-mq_{k-1}\right)\Phi\left(\sum_{i=1}^{n}q_{i}x_{i}-x_{k-1}\right)+m\left(p_{k}-mq_{k}\right)\Phi\left(x_{k}-\sum_{i=1}^{n}q_{i}x_{i}\right).$

Hence (LABEL:3.9) holds and the proof of the theorem is complete. ∎

In Theorem 9 we get a refinement of the left handside of the inequality (5) in
Theorem 5 for $\Phi$-uniformly convex functions:

######  Theorem 9.

Let $f$ be $\Phi$-uniformly convex. Then the inequality

$\displaystyle
p_{1}f\left(a\right)+p_{2}f\left(b\right)-f\left(p_{1}a+p_{2}b\right)-m\left(q_{1}f\left(a\right)+q_{2}f\left(b\right)-f\left(q_{1}a+q_{2}b\right)\right)$
$\displaystyle\geq$ $\displaystyle
m\left(p_{2}-mq_{2}\right)\Phi\left(q_{1}\left(b-a\right)\right)=m\left(1-m\right)\Phi\left(q_{1}\left(b-a\right)\right)$

holds when $\frac{p_{1}}{q_{1}}=m\leq\frac{p_{2}}{q_{2}}$, $p_{i}\geq 0$,$\
q_{i}>0$, $i=1,2$, $p_{1}+p_{2}=q_{1}+q_{2}=1$.

In the special case for $q_{1}=q_{2}=\frac{1}{2}$ we get the inequality

$\displaystyle
p_{1}f\left(a\right)+p_{2}f\left(b\right)-f\left(p_{1}a+p_{2}b\right)-2p_{1}\left[\frac{f\left(a\right)+f\left(b\right)}{2}-f\left(\frac{a+b}{2}\right)\right]$
$\displaystyle\geq$ $\displaystyle
2p_{1}\left(1-2p_{1}\right)\Phi\left(\frac{b-a}{2}\right),$

and the maximum of the right handside of (9) is obtained when
$p_{1}=\frac{1}{4}$ and (9) is

$\displaystyle\frac{1}{4}f\left(a\right)+\frac{3}{4}f\left(b\right)-f\left(\frac{1}{4}a+\frac{3}{4}b\right)$
$\displaystyle-\frac{1}{2}\left(\frac{f\left(a\right)+f\left(b\right)}{2}-f\left(\frac{a+b}{2}\right)\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{4}\Phi\left(\frac{x_{2}-x_{1}}{2}\right).$

###### Proof.

The left handside of (9) can be rewritten when $\frac{p_{1}}{q_{1}}=m$,$\
x_{1}=a$, $x_{2}=b$ as

$\left(p_{2}-mq_{2}\right)f\left(x_{2}\right)+mf\left(q_{1}x_{1}+q_{2}x_{2}\right)-f\left(p_{1}x_{1}+p_{2}x_{2}\right)$

Denoting

(3.15) $d_{1}=m,$ | $y_{1}=q_{1}x_{1}+q_{2}x_{2}$
---|---
$d_{2}=p_{2}-mq_{2},$ | $y_{2}=x_{2},$

we take into consideration that
$\frac{p_{1}}{q_{1}}=m\leq\frac{p_{2}}{q_{2}}$, and because
$\sum_{i=1}^{2}p_{i}x_{i}=\sum_{i=1}^{2}d_{i}y_{i}$ we get from (3.15) and
Definition 1 that the following inequality holds:

$\displaystyle
p_{1}f\left(x_{1}\right)+p_{2}f\left(x_{2}\right)-f\left(p_{1}x_{1}+p_{2}x_{2}\right)$
$\displaystyle-m\left(q_{1}f\left(x_{1}\right)+q_{2}f\left(x_{2}\right)-f\left(q_{1}x_{1}+q_{2}x_{2}\right)\right)$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{2}d_{i}f\left(y_{i}\right)-f\left(\sum_{i=1}^{2}d_{i}y_{i}\right)$
$\displaystyle=$ $\displaystyle
mf\left(q_{1}x_{1}+q_{2}x_{2}\right)+\left(p_{2}-mq_{2}\right)f\left(x_{2}\right)$
$\displaystyle\geq$ $\displaystyle
m\left(p_{2}-mq_{2}\right)\Phi\left(\left(x_{2}-x_{1}\right)q_{1}\right)$
$\displaystyle=$
$\displaystyle\frac{p_{1}}{q_{1}}\left(1-p_{1}-\frac{p_{1}}{q_{1}}q_{2}\right)\Phi\left(q_{1}\left(x_{2}-x_{1}\right)\right)$
$\displaystyle=$ $\displaystyle
m\left(1-m\right)\Phi\left(q_{1}\left(x_{2}-x_{1}\right)\right).$

Hence, (9) is proved and therefore also (9). The maximum of the right handside
of (9) is obtained when $p_{1}=\frac{1}{4}$ therefore the right handside of
(9) gives the best refinement of the left handside of (5) in Theorem 5 for
$\Phi$-uniformly convex functions. ∎

######  Remark 4.

Inequality (7) is a refinement of the left handside of (5). However when
$\frac{\Phi\left(x\right)}{x^{2}}$ is increasing, it is a weaker refinement
than the refinement (9) in Theorem 9 obtained from Definition 1.

When we take $f\left(x\right)\ $to be
$f\left(x\right)=\Phi\left(x\right)=x^{2}$, $x\geq 0$ we get an equality all
over Theorem 7 for all $n=2,3,...$. But in Theorem 8 we get always equality
only for $f\left(x\right)=\Phi\left(x\right)=x^{2}$, for $n=2$.

## References

  * [1] S. Abramovich, ”Refinement of Jensen’s inequality by uniformly convex functions”, Aequationes Mathematicae. 97 no. 1, (2023), 75-88.
  * [2] S. Abramovich, ”On generalized Convexity and Superquadracity”,a chapter in: Optimization and Application, Mathematical Analysis in Interdisciplinary Research, Vol. 179, Springer, (2021), appeared electronically in March 2022.
  * [3] S. Abramovich and S. S. Dragomir, ”Normalized Jensen Functional, Superquadracity and Related Inequalities”, International Series of Numerical Mathematics, Birkhäuser Verlag, 157, (2008) p-p 217-228.
  * [4] J. Barić, M. Matić, J. Pečarić, ”On the bounds for the normalized Jensen functional and Jensen-Steffensen Inequality”, Math. Inequal. Appl. 12, (2009), no 2, 413-432.
  * [5] S. S. Dragomir, ”Bounds of the normalised Jensen functional”, Bull. Austral. Math. Soc., 74 (2006), 471-478.
  * [6] S. Simić and B. Almohsen, ”Some generalization of Jensen’s inequality”, Contemporary Mathematics, 2020, pp. 14.
  * [7] Y. Sayyari, ” New entropy bounds via uniformly convex functions”, Chaos, Solitons and Fractals, 141 (2020), 110360.
  * [8] M. Niezgoda, ”An extension of Levin-Steckin’s theorem to uniformly convex and superquadratic functions”, Aequat. Math. 94 (2020), 303-321
  * [9] C. Zalinescu, ”On uniformly convex functions”, J. Math. Anal. Appl., 95 (1983) 344-374.


# Packing $T$-connectors in graphs needs more connectivity

Roman Čada 1 Adam Kabela 1 Tomáš Kaiser 1 Petr Vrána 1

###### Abstract

Strengthening the classical concept of Steiner trees, West and Wu [J. Combin.
Theory Ser. B 102 (2012), 186–205] introduced the notion of a $T$-connector in
a graph $G$ with a set $T$ of terminals. They conjectured that if the set $T$
is $3k$-edge-connected in $G$, then $G$ contains $k$ edge-disjoint
$T$-connectors. We disprove this conjecture by constructing infinitely many
counterexamples for $k=1$ and for each even $k$.

11footnotetext: Department of Mathematics and European Centre of Excellence
NTIS (New Technologies for the Information Society), University of West
Bohemia, Pilsen, Czech Republic. E-mail:
<EMAIL_ADDRESS>Supported by project GA20-09525S of
the Czech Science Foundation.

##  1 Introduction

Let $G$ be a graph and $T\subseteq V(G)$ a set of vertices called _terminals_.
The vertices in $V(G)\setminus T$ are the _non-terminals_. For brevity, we may
call the pair $(G,T)$ a _graph with terminals_.

A _$T$ -tree_ (or _Steiner tree_) in $G$ is a tree whose vertex set includes
every vertex from $T$. Kriesell [4] investigated the existence of edge-
disjoint $T$-trees in relation to the connectivity of $T$ in $G$, defined as
follows. The set $T$ is said to be _$k$ -edge-connected_ in $G$ if $G$
contains no edge-cut of size smaller than $k$ separating two vertices from
$T$. Note that this entails no assumption about the connectivity of $G$
itself. Kriesell [4] conjectured that if $T$ is $2k$-edge-connected in $G$,
then $G$ contains $k$ edge-disjoint $T$-trees. This conjecture is still open
but DeVos, McDonald and Pivotto [2] proved that the conclusion holds if $T$ is
$(5k+4)$-connected in $G$ (see also [5, 6] for earlier results).

In this paper, we deal with related objects called $T$-connectors, introduced
by West and Wu [6]. Recall first that a _$T$ -path_ in $G$ is a path whose
both endvertices belong to $T$ but which is otherwise disjoint from $T$. The
operation of _short-cutting_ a nontrivial path $P$ consists in removing all
edges of $P$ and adding an edge joining its endvertices. A _$T$ -connector_ in
$G$ is the union of a family of edge-disjoint $T$-paths in $G$ such that if we
shortcut the $T$-paths one by one, we obtain a graph whose induced subgraph on
$T$ is connected. Improving upon a result of [6], DeVos et al. [2] proved that
$G$ has $k$ edge-disjoint $T$-connectors provided that $T$ is $(6k+6)$-edge-
connected in $G$.

On the other hand, West and Wu [6] constructed examples of graphs with
terminals $(G,T)$ such that $T$ is $(3k-1)$-edge-connected in $G$, but $G$
does not admit $k$ edge-disjoint $T$-connectors. They conjectured that higher
edge-connectivity of $T$ already implies the existence of $k$ edge-disjoint
$T$-connectors.

######  Conjecture 1.1.

Let $k$ be a positive integer and $(G,T)$ a graph with terminals. If $T$ is
$3k$-edge-connected in $G$, then $G$ admits $k$ pairwise edge-disjoint
$T$-connectors.

We disprove Conjecture 1.1. Surprisingly, it turns out that there is a
counterexample already for the case $k=1$. More generally, we provide an
infinite family of counterexamples for $k=1$ and for each even $k$. Our main
result is the following.

######  Theorem 1.2.

For any nonnegative integer $\ell$, there are infinitely many graphs with
terminals $(G,T)$ such that

  1. (1)

$T$ is $(3\cdot 2^{\ell})$-edge-connected in $G$, and

  2. (2)

$G$ does not admit $2^{\ell}$ edge-disjoint $T$-connectors.

The plan of the paper is as follows. In Section 2, we recall some necessary
notions and prove a useful technical lemma on gluing graphs with terminals
(Lemma 2.1). Section 3 describes the construction of the counterexamples
$(G_{\ell},T_{\ell})$ for the case where $k=2^{\ell}$ is a power of two. The
same assumption that $k$ is a power of two is used in Sections 4 and 5. In
Section 4, we show that if $G_{\ell}$ contains $k$ edge-disjoint
$T_{\ell}$-connectors, then these $T_{\ell}$-connectors can be chosen so as to
satisfy certain additional properties in relation to the edge-cuts in
$G_{\ell}$. In Section 5, we prove the main result. Finally, we discuss in
Section 6 how the construction is adapted to the case where $k$ is an even
integer which is not a power of two.

##  2 Preliminaries

If $n$ is a positive integer, we let $[n]$ denote the set
$\left\\{{1,\dots,n}\right\\}$. Throughout this paper, parallel edges are
allowed in graphs. A path $P$ in a graph $G$ is said to be an _$uv$ -path_ if
its endvertices are $u$ and $v$.

If $G$ is a graph and $X\subseteq V(G)$, then the symbol $\partial_{G}({X})$
denotes the set of all edges of $G$ with exactly one endvertex in $X$. The
_degree_ of $X$ in $G$, denoted by $d_{G}(X)$, is defined as
$\left|\partial_{G}({X})\right|$. We abbreviate $d_{G}(\left\\{{v}\right\\})$
to $d_{G}(v)$.

In order to break down the construction into steps, we define an insertion
operation as follows. Let $(G_{1},T_{1})$ and $(G_{2},T_{2})$ be disjoint
graphs with terminals, let $t_{1}\in T_{1}$ and $t_{2}\in T_{2}$ be terminals
of equal degree, and let
$h:\,\partial_{G_{1}}({t_{1}})\to\partial_{G_{2}}({t_{2}})$ be a bijection.
The _insertion_ of $G_{2}$ into $G_{1}$ via $h$ is the graph with terminals
$G_{1}\circ_{h}G_{2}$ obtained as follows:

  * •

we start with the disjoint union of $G_{1}-t_{1}$ and $G_{2}-t_{2}$,

  * •

for each $e\in\partial_{G_{1}}({t_{1}})$, we add an edge joining the endvertex
of $e$ distinct from $t_{1}$ to the endvertex of $h(e)$ distinct from $t_{2}$,

  * •

the set of terminals in the resulting graph is $T_{1}\cup
T_{2}\setminus\left\\{{t_{1},t_{2}}\right\\}$.

To keep things simple, we let the vertices $t_{1}$ and $t_{2}$ be implicit in
the symbol $h$ in $G_{1}\circ_{h}G_{2}$, and we do not include the sets
$T_{1},T_{2}$ in the notation.

The following lemma helps us to control the connectivity of terminals in
graphs obtained by insertion.

######  Lemma 2.1.

Let $(G_{1},T_{1})$ and $(G_{2},T_{2})$ be disjoint graphs with terminals. For
each $i$ in $\left\\{{1,2}\right\\}$, suppose that $\left|T_{i}\right|\geq 2$
and $T_{i}$ is $d$-edge-connected in $G_{i}$, and let $t_{i}\in T_{i}$ be a
terminal of degree $d$. For a bijection
$h:\,\partial_{G_{1}}({t_{1}})\to\partial_{G_{2}}({t_{2}})$, let $(G,T)$
denote the graph with terminals $G_{1}\circ_{h}G_{2}$. Then $T$ is $d$-edge-
connected in $G$.

###### Proof.

For $v_{1},v_{2}\in T$, we want to find $d$ edge-disjoint $v_{1}v_{2}$-paths
in $G$. By symmetry, we may assume that $v_{1}\in T_{1}$. We discuss two
cases.

Suppose first that $v_{2}\in T_{2}$. Since $T_{1}$ is $d$-edge-connected in
$G_{1}$, we can choose edge-disjoint $v_{1}t_{1}$-paths $P_{1},\dots,P_{d}$ in
$G_{1}$. Similarly, we choose edge-disjoint $v_{2}t_{2}$-paths
$Q_{1},\dots,Q_{d}$ in $G_{2}$. For $i\in[d]$, let $e_{i}$ be the edge of
$P_{i}$ incident with $t_{1}$ and consider the unique path $Q_{j}$ containing
the edge $h(e_{i})$. Glue $P_{i}$ and $Q_{j}$ by removing $t_{1}$ and $t_{2}$
and adding an edge of $G$ that joins the new endvertices of these shortened
paths (that is, an edge of $G$ connecting the endvertices of $e_{i}$ and
$h(e_{i})$ other than $t_{1}$ and $t_{2}$). Note that this gives $d$ edge-
disjoint $v_{1}v_{2}$-paths in $G$.

For the second case, suppose that $v_{2}\in T_{1}$. Let $R_{1},\dots,R_{d}$ be
edge-disjoint $v_{1}v_{2}$-paths in $G_{1}$. If none of them contains the
vertex $t_{1}$, then $R_{1},\dots,R_{d}$ are the sought paths in $G$. Thus,
assume that some of the paths, say $R_{1},\dots,R_{c}$, contain $t_{1}$. Note
that $c\leq\frac{d}{2}$ since $t_{1}$ is an internal vertex for each of these
edge-disjoint paths and $t_{1}$ has degree $d$ in $G_{1}$. Since
$\left|T_{2}\right|\geq 2$, we may choose $w_{2}\in
T_{2}\setminus\left\\{{t_{2}}\right\\}$ and choose a set $\mathcal{S}$ of $d$
edge-disjoint $w_{2}t_{2}$-paths in $G_{2}$. For each $i\in[c]$, we combine
$R_{i}$ with two paths from $\mathcal{S}$ and obtain a $v_{1}v_{2}$-path
$R^{\prime}_{i}$ in $G$ as follows.

Let $i\in[c]$ and $e_{i,1},e_{i,2}$ be the two edges of $R_{i}$ incident with
$t_{1}$. For $j\in\left\\{{1,2}\right\\}$, let $S_{i,j}$ be the unique
$w_{2}t_{2}$-path containing $h(e_{i,j})$ and let $s_{i,j}$ be the neighbour
of $t_{2}$ on $S_{i,j}$. Although $S_{i,1}$ and $S_{i,2}$ are edge-disjoint,
$S_{i,1}\cup S_{i,2}-t_{2}$ need not be a path in $G_{2}$ because of vertices
of degree $4$. However, it is easy to see that $S_{i,1}\cup S_{i,2}$ contains
an $s_{i,1}s_{i,2}$-path $S^{\prime}_{i}$. Take the two parts of $R_{i}-t_{1}$
and the path $S^{\prime}_{i}$, and glue them together by adding the edges that
join the endvertices of $S^{\prime}_{i}$ and the corresponding vertices of
$R_{i}-t_{1}$ to obtain a $v_{1}v_{2}$-path $R^{\prime}_{i}$. The paths
$R^{\prime}_{1},\dots,R^{\prime}_{c},R_{c+1},\dots,R_{d}$ are edge-disjoint
$v_{1}v_{2}$-paths in $G$ as required. ∎

##  3 The construction for $k$ a power of two

Let $\ell\geq 0$ and set $k=2^{\ell}$. We construct a graph $G_{\ell}$ and a
set of terminals $T_{\ell}\subseteq V(G_{\ell})$ satisfying the properties in
Theorem 1.2. The construction is in several steps. In each of the graphs with
terminals we construct, all terminals have degree $3k$ and all non-terminals
have degree $3$. Moreover, one of the terminals is usually designated as the
_root_ terminal $r$ and the edges incident with $r$ are partitioned into three
_classes_ denoted by $A$, $B$, $C$.

Let us first describe the construction for $\ell\geq 1$ and then comment on
the (much simpler) case $\ell=0$.

Step 1. In steps 1–2, we describe the graphs with terminals $(F_{i},T_{i})$,
where $0\leq i\leq\ell-1$. The graph $F_{0}$ consists of two terminals joined
by $3k$ parallel edges. One of the terminals is the root, and the partition of
the edges into $A$, $B$, $C$ is arbitrary, with $C$ containing a single edge
(the _output edge_) and the sizes of $A$ and $B$ being $\frac{3}{2}k$ and
$\frac{3}{2}k-1$, respectively.

Step 2. For $i>0$, $(F_{i},T_{i})$ is shown in Figure 1. The partition of the
edges incident with the root is shown by edge labels $A$, $B$, $C$. The sizes
of these classes are $\frac{3}{2}k$, $\frac{3}{2}k-2^{i}$ and $2^{i}$,
respectively. (Note that this is consistent with the case $i=0$.) The edges of
type $C$ are the _output edges_ of $F_{i}$.

Step 3. The graph with terminals $(F^{*}_{i},T^{*}_{i})$ ($0\leq i\leq\ell-1$)
is constructed as follows. First, $(F^{*}_{0},T^{*}_{0})=(F_{0},T_{0})$.
Assume then that $i>0$ and that $(F^{*}_{i-1},T^{*}_{i-1})$ has already been
constructed.

The graph with terminals $(F^{*}_{i},T^{*}_{i})$ is obtained by inserting one
copy of $(F^{*}_{i-1},T^{*}_{i-1})$ at the terminal $f_{1}$ of $F_{i}$, and
another copy at the terminal $f_{2}$. In the graph $F^{*}_{i-1}$, the
insertion involves the root terminal $r$. More precisely, let $h_{1}$ be a
bijection between $\partial_{F_{i}}({f_{1}})$ and
$\partial_{F^{*}_{i-1}}({r})$ which maps the edges between $f_{1}$ and
$u_{1}^{A}$ to class $A$ edges, the edges between $f_{1}$ and $u_{1}^{B}$ to
class $B$ edges, and the remaining edges incident with $f_{1}$ to class $C$
edges. (Note that the edge counts match: $\frac{3}{2}k$,
$\frac{3}{2}k-2^{i-1}$ and $2^{i-1}$, respectively.) Let $h_{2}$ be an
analogous bijection for $f_{2}$ (and $r$) in the place of $f_{1}$ (and $r$),
with $u_{2}^{A}$ playing the role of $u_{1}^{A}$ etc.

We define $(F^{*}_{i},T^{*}_{i})$ as the result of inserting $F^{*}_{i-1}$
into $F_{i}$ at $f_{1}$ via $h_{1}$, followed by the insertion of
$F^{*}_{i-1}$ at $f_{2}$ via $h_{2}$. The root terminal of $F^{*}_{i}$ is
defined as identical with that of $F_{i}$, and so is its partition of the
incident edges into the classes $A,B,C$ and its set of _output edges_.

Step 4. As the next step, we use the graph with terminals
$(F_{\ell},T_{\ell})$ shown in Figure 2 to construct
$(F^{*}_{\ell},T^{*}_{\ell})$. This involves six insertions of
$F^{*}_{\ell-1}$ into $F_{\ell}$ at terminals from the set

$\left\\{{f_{12},f_{21},f_{23},f_{32},f_{31},f_{13}}\right\\}.$

For the insertion, say, at $f_{12}$, we choose any bijection mapping the
$\frac{3}{2}k$ edges between $f_{12}$ and $w_{1}$ to class $A$ edges of
$F^{*}_{\ell-1}$, the $\frac{k}{2}$ edges between $f_{12}$ and the root of
$F_{\ell}$ to the class $C$ edges, and the remaining $k$ edges to class $B$
edges. (For the other insertions, the choice of bijection is similar, the only
difference being that $w_{1}$ may be replaced by $w_{2}$ or $w_{3}$.) Note
that $\frac{k}{2}=2^{\ell-1}$, so the bijection exists indeed. The resulting
graph with terminals is $(F^{*}_{\ell},T^{*}_{\ell})$. Its root terminal is
defined to be the same as in $F_{\ell}$.

Step 5. In the last two steps, we construct the graph with terminals
$(G_{\ell},T_{\ell})$. Let $N$ be a $3$-connected non-hamiltonian cubic
bipartite graph [3] (see also [1]), with colour classes $X$ and $Y$. Perform
the following steps:

  * •

construct a bipartite graph $N^{\prime}$ by replacing each vertex $y\in Y$
with an independent set $y_{1},\dots,y_{k}$ of non-terminals, each adjacent to
the neighbours of $y$, and declaring the vertices in $X$ (now of degree $3k$)
terminals,

  * •

insert one copy of $F^{*}_{\ell}$ at each vertex $x\in X$ in $N^{\prime}$ via
a bijection $h$ between the set of $3k$ edges incident with $x$ and the set of
$3k$ edges incident with the root terminal of $F^{*}_{\ell}$ (which is the
vertex of $F^{*}_{\ell}$ used for each insertion); $h$ is chosen such that for
each neighbour $y$ of $x$ in $N$, all the $k$ edges of $N^{\prime}$
corresponding to the edge $xy$ are mapped to the $k$ edges incident with $r$
and a vertex from $\\{f_{pq},f_{qp}\\}$, for suitable $1\leq p<q\leq 3$.

Step 6. Finally, insert a copy of $K_{3,3k}$ (with $3$ terminals of degree
$3k$, one of which is chosen as the root) at every terminal $t$ of the
resulting graph. For the insertion, use an arbitrary bijection between the
respective edge sets. Each insertion creates one induced copy of $K_{2,3k}$
(containing two terminals); the vertex sets of these copies will be called
_atoms_ of $G_{\ell}$. We define a set $Y\subseteq V(G_{\ell})$ to be
_aligned_ if every atom of $G_{\ell}$ is either contained in $Y$ or disjoint
from $Y$.

Figure 1: The graph with terminals $(F_{i},T_{i})$, where $1\leq i\leq\ell-1$.
Terminals are shown by black dots. A white square with a grey numerical label
represents an independent set of non-terminals of the given size, with each
non-terminal joined by edges to all the terminals adjacent to the square mark.
Labels on edges between terminals represent parallel edges of the given
multiplicity. The root is the middle vertex. Labels on the adjacent edges
represent the partition into the classes $A$, $B$, $C$. Figure 2: The graph
with terminals $(F_{\ell},T_{\ell})$ when $\ell\geq 1$. The same conventions
as in Figure 1 apply. The root is the middle vertex.

As remarked before the construction, all terminals in the above graphs have
degree $3k$ and all non-terminals have degree $3$. Moreover, we have the
following consequence of Lemma 2.1.

######  Observation 3.1.

The set $T_{\ell}$ is $3k$-edge-connected in $G_{\ell}$.

###### Proof.

The set $T_{i}$ is $3k$-edge-connected in $F_{i}$ by direct inspection, for
$0\leq i\leq\ell$. Similarly, the set of terminals is $3k$-edge-connected in
the graph $N^{\prime}$ created in step 5 of the construction (since $N$ is
$3$-connected) and the same applies to $K_{3,3k}$ used in step 6. Thus, the
observation follows from iterated use of Lemma 2.1. ∎

As promised, we now turn to the case $\ell=0$ (corresponding to $k=1$). In
this case, steps 1–4 may be skipped completely and we can start with the
$3$-connected non-hamiltonian cubic bipartite graph $N$ of step 5. We do not
need to perform any insertions in this step, just regard the colour class $X$
as terminals and the colour class $Y$ as non-terminals. Step 6 is performed as
described in the construction, i.e., a copy of $K_{3,3}$ is inserted at each
terminal.

##  4 Choosing the connectors

Recall that $k=2^{\ell}$ and consider the graph with terminals
$(G_{\ell},T_{\ell})$ constructed in Section 3. Recall that all terminals of
$G_{\ell}$ have degree $3k$ and all non-terminals have degree $3$. As shown in
Observation 3.1, $T_{\ell}$ is $3k$-edge-connected in $G_{\ell}$.

An edge-cut $R$ in $G_{\ell}$ is said to be _basic_ if there is an independent
set $X_{0}\subseteq V(G_{\ell})$ consisting of non-terminals such that the
following holds for the partition $\mathcal{P}$ of $V(G_{\ell})\setminus
X_{0}$ into vertex sets of connected components of $G_{\ell}-X_{0}$:

  * •

for each $X\in\mathcal{P}$, $d_{G_{\ell}}(X)=3k$.

  * •

$R=\partial_{G_{\ell}}({Y})$ for some $Y\in\mathcal{P}$,

  * •

each set in $\mathcal{P}$ is aligned and contains at least one terminal,

In this situation, we say that $R$ is a basic edge-cut _for $X_{0}$_.

######  Observation 4.1.

If $X$ is an atom in $G_{\ell}$, then the edge-cut $\partial_{G_{\ell}}({X})$
is basic.

###### Proof.

Let $X_{0}$ be the set of non-terminals in $X$. Observe that $G_{\ell}-X_{0}$
has precisely three components: two of them are singletons containing the
terminals in $X$, and the third one is $G_{\ell}-X$. (The connectedness of
$G_{\ell}-X$ follows from the fact that the graph entering step 6 of the
construction of $G_{\ell}$ is 2-connected.) It is routine to check the
conditions in the definition of a basic edge-cut. ∎

######  Lemma 4.2.

Let $\ell\geq 0$ and let $k=2^{\ell}$. Consider the graph with terminals
$(G_{\ell},T_{\ell})$ and let $r\in T_{\ell}$. If Conjecture 1.1 holds for the
given value of $k$, then there exist edge-disjoint $T_{\ell}$-connectors
$Q_{1},\dots,Q_{k}$ in $G_{\ell}$ with the following properties:

  1. (i)

$Q:=Q_{1}\cup\dots\cup Q_{k}$ contains exactly $2k$ edges in each basic edge-
cut of $G_{\ell}$,

  2. (ii)

$Q$ contains at least $2k$ edges of $\partial_{G_{\ell}}({A})$, where $A$ is
any aligned set of vertices of $G_{\ell}-r$,

  3. (iii)

for each $i\in[k]$, $Q_{i}-r$ is connected.

###### Proof.

Let $H$ be a $3$-connected cubic graph with more than $2k$ vertices. Replace
each edge of $H$ with $k$ parallel edges and regard all vertices of the
resulting $3k$-regular graph $kH$ as terminals. Let ($H^{\prime},T^{\prime})$
be obtained by inserting, one by one, a copy of $(G_{\ell},T_{\ell})$ at each
vertex of $kH$. The terminal $r$ of $G_{\ell}$ from the statement of the lemma
is used for the insertions, while the bijection between the edge sets is
arbitrary. The copy of $G_{\ell}-r$ in $H^{\prime}$ created by the insertion
of $G_{\ell}$ at $w\in V(kH)$ will be denoted by $G^{w}$. Furthermore, in what
follows, any atom in each such copy of $G_{\ell}-r$ will be referred to as an
atom of $H^{\prime}$.

######  Claim 1.

The set $T^{\prime}$ is $3k$-edge-connected in $H^{\prime}$.

This follows directly from Lemma 2.1 since $kH$ is clearly $3k$-edge-connected
and $T_{\ell}$ is $3k$-edge-connected in $G_{\ell}$ by Observation 3.1.

Assuming the truth of Conjecture 1.1 for $k$, suppose that there exist
$T^{\prime}$-connectors $Q^{\prime}_{1},\dots,Q^{\prime}_{k}$ in $H^{\prime}$.
Let these $T^{\prime}$-connectors be chosen so as to

  1. (Q1)

minimise the total number of edges of $Q^{\prime}:=Q^{\prime}_{1}\cup\dots\cup
Q^{\prime}_{k}$,

  2. (Q2)

subject to (Q1), maximise the total number of edges of $Q^{\prime}$ with both
endvertices in the same atom.

Observe that by minimality with respect to (Q1) and by the fact that each non-
terminal in $H^{\prime}$ has degree $3$, each $Q^{\prime}_{i}$ is a tree.

######  Claim 2.

For any $i\in[k]$ and any atom $X$, the induced subgraph $Q^{\prime}_{i}[X]$
contains a path joining the two terminals in $X$.

We prove the claim by contradiction. Suppose that the two terminals $x,y\in X$
are not joined by a path in $Q^{\prime}_{i}[X]$. Let $P$ be the unique path in
the tree $Q^{\prime}_{i}$ joining $x$ to $y$, and let $P_{0}$ be the subpath
of $P$ starting at $x$ and ending at the first terminal different from $x$.
Let $u$ be the non-terminal adjacent to $x$ on $P_{0}$, and let
$Q^{\prime\prime}_{i}$ be obtained by removing the edges of $P_{0}$ from
$Q^{\prime}_{i}$ and adding the edges $xu,uy$. Clearly, $Q^{\prime\prime}_{i}$
is a tree and a $T^{\prime}$-connector; since the length of $P_{0}$ is at
least $2$, $Q^{\prime\prime}_{i}$ has at most as many edges as
$Q^{\prime}_{i}$, and has more edges with both endvertices in $X$ than
$Q^{\prime}_{i}$ does, contradicting the choice of
$Q^{\prime}_{1},\dots,Q^{\prime}_{k}$ with respect to (Q2).

######  Claim 3.

If $X$ is an atom of $H^{\prime}$, then $d_{Q^{\prime}}(X)\leq 2k$.

Let $x,y$ be the terminals of $X$. Since each $Q^{\prime}_{i}$ ($i\in[k]$)
contains an $xy$-path of length two by Claim 2, at least $k$ of the edges in
$\partial_{H^{\prime}}({X})$ are not used by $Q^{\prime}$. This proves the
claim since $d_{H^{\prime}}(X)=3k$.

In the proofs of the following two claims, we will consider a modification of
the connectors $Q^{\prime}_{i}$. For $i\in[k]$, let $\tilde{Q}_{i}$ be the
multigraph obtained from $Q^{\prime}_{i}$ by the following procedure:

  * •

identify all the vertices of each atom $X$ to a single vertex $v_{X}$ (keeping
any parallel edges and discarding loops),

  * •

suppress any remaining non-terminals whose degree in $Q^{\prime}_{i}$ is $2$
and delete those whose degree in $Q^{\prime}_{i}$ is $0$.

Note that all the multigraphs $\tilde{Q}_{i}$ are trees on the same vertex
set, namely the set of vertices $v_{X}$ corresponding to the atoms $X$ of
$H^{\prime}$. Let $\tilde{Q}$ be the union of all $\tilde{Q}_{i}$ over
$i\in[k]$.

######  Claim 4.

There is a vertex $w\in V(kH)$ such that if $X$ is any atom of $H^{\prime}$
contained in $V(G^{w})$, then $d_{Q^{\prime}}(X)=2k$.

Let $n$ be the number of vertices of the multigraph $\tilde{Q}$ defined above.
Since $\tilde{Q}$ is the union of $k$ edge-disjoint trees on these $n$
vertices, it has $k(n-1)$ edges and therefore

$\sum_{t\in V(\tilde{Q})}d_{\tilde{Q}}(t)=2k(n-1).$ (1)

On the other hand, Claim 3 implies that for each $t\in V(\tilde{Q})$,
$d_{\tilde{Q}}(t)\leq 2k$. In view of (1), there can be at most $2k$ vertices
of $\tilde{Q}$ whose degree in $\tilde{Q}$ is strictly smaller than $2k$.
Since $\left|V(H)\right|>2k$, where $H$ is the cubic graph used to construct
$H^{\prime}$, the claim follows.

######  Claim 5.

Let $Y$ be an aligned subset of $V(G^{w})$, where $w$ is as in Claim 4. For
$i\in[k]$, let $\kappa_{i}$ be the number of components of $Q^{\prime}_{i}[Y]$
containing at least one edge each. Then

$d_{Q^{\prime}}(Y)=2\cdot\sum_{i=1}^{k}\kappa_{i}.$ (2)

In particular, $d_{Q^{\prime}}(Y)\geq 2k$.

Consider the multigraph $\tilde{Q}$ and let $D$ be the sum of
$d_{\tilde{Q}}(X)$, taken over all atoms $X$ with $X\subseteq Y$. By Claim 4,
$D=2kn$, where $n$ is the number of such atoms. We evaluate $D$ in another
way.

Fix $i\in[k]$ and let $\delta_{i}$ be the number of edges of $\tilde{Q}_{i}$
with one endvertex corresponding to an atom in $Y$ and one to an atom outside
$Y$. Observe that $\sum_{i=1}^{k}\delta_{i}=d_{Q^{\prime}}(Y)$. Furthermore,
the number of edges of $\tilde{Q}_{i}$ with both endvertices corresponding to
atoms in $Y$ is $n-\kappa_{i}$. It follows that

$D=\sum_{i=1}^{k}\Bigl{(}2\cdot(n-\kappa_{i})+\delta_{i}\Bigr{)}=2kn-2\sum_{i=1}^{k}\kappa_{i}+d_{Q^{\prime}}(Y).$

Since $D=2kn$, equation (2) follows. In addition, since $\kappa_{i}\geq 1$ for
each $i\in[k]$, the right hand side of (2) is greater than or equal to $2k$.
This proves the claim.

To obtain the sought $T_{\ell}$-connectors in $G_{\ell}$, take $w$ as in Claim
4 and contract the complement of $V(G^{w})$ in $H^{\prime}$ to a single
terminal $r$ of degree $3k$. The resulting graph with terminals is a copy of
$(G_{\ell},T_{\ell})$. To simplify the notation, we will in fact identify it
with $(G_{\ell},T_{\ell})$ in the rest of this proof. Note that by the
construction of $H^{\prime}$, the vertex $r$ obtained by the contraction is
precisely the terminal of $G_{\ell}$ selected in the statement of the lemma.

Define $Q_{1},\dots,Q_{k}$ as the subgraphs of $G_{\ell}$ obtained from
$Q^{\prime}_{1},\dots,Q^{\prime}_{k}$ by this contraction (note that these are
not necessarily trees) and let $Q$ denote their union. It is easy to see that
each $Q_{i}$ ($i\in[k]$) is a $T_{\ell}$-connector in $G_{\ell}$.

######  Claim 6.

The graph $Q$ contains exactly $2k$ edges from each basic edge-cut in
$G_{\ell}$.

Given a basic edge-cut $R$ in $G_{\ell}$ for a set $X_{0}$ of non-terminals,
let $\mathcal{P}$ be the partition of $V(G_{\ell})\setminus X_{0}$ as in the
definition of basic edge-cut, and let $p=\left|\mathcal{P}\right|$. For any
$X\in\mathcal{P}$, the set $\partial_{G_{\ell}}({X})$ contains $3k$ edges,
each of which is incident with a degree $3$ vertex in the independent set
$X_{0}$. It follows that $\left|X_{0}\right|=kp$.

We claim that for any $Y\in\mathcal{P}$, $d_{Q}(Y)\geq 2k$. If $r\notin Y$,
then this follows from Claim 5 since $Y$ is then an aligned set of vertices of
$G^{w}$, and we have $d_{Q}(Y)=d_{Q^{\prime}}(Y)$. On the other hand, if $r\in
Y$, then we apply Claim 5 to the complement of $Y$ in $V(G_{\ell})$ (which is
also aligned) and get the same conclusion.

Consequently, we obtain $\sum_{X\in\mathcal{P}}d_{Q}(X)\geq 2kp$. On the other
hand, each of the $kp$ vertices of $X_{0}$ has degree at most $2$ in $Q$, so
equality holds and $d_{Q}(X)=2k$ for any $X\in\mathcal{P}$. This implies the
claim.

Properties (i) and (ii) in the lemma follow from Claim 6 and Claim 5,
respectively. It remains to prove property (iii).

We first prove that $Z:=\partial_{G_{\ell}}({\left\\{{r}\right\\}})$ is a
basic edge-cut in $G_{\ell}$. Let $N$ be the non-hamiltonian cubic bipartite
graph used to construct $G_{\ell}$. Recall that $N$ has colour classes $X$ and
$Y$ and during the construction, each vertex of $Y$ is replaced by an
independent set of non-terminals of degree $3$ and a copy of $F^{*}_{\ell}$ is
inserted at each of the remaining vertices. We define $X_{0}$ as the set of
non-terminals arising from the former operation, and observe that $Z$
satisfies the properties of a basic edge-cut for $X_{0}$.

By Claim 6, $Q$ contains $2k$ edges of $Z$. Thus, Claim 5 (used with
$Y=V(G^{w})$) implies that for each $i\in[k]$, the induced subgraph of
$Q^{\prime}_{i}$ on $V(G_{\ell})$ must have exactly one component — that is,
$Q_{i}-r$ is connected. ∎

##  5 Proof of Theorem 1.2

In this section, we prove our main result.

######  Theorem 1.2.

For any integer $\ell\geq 0$, there are infinitely many graphs with terminals
$(G,T)$ such that

  1. (1)

$T$ is $3\cdot 2^{\ell}$-edge-connected in $G$, and

  2. (2)

there do not exist $2^{\ell}$ edge-disjoint $T$-connectors in $G$.

###### Proof.

Let $\ell\geq 0$ be given and let $k=2^{\ell}$. Let $(G_{\ell},T_{\ell})$ be
the graph with terminals constructed in Section 3. The construction uses a
$3$-connected non-hamiltonian bipartite cubic graph $N$; by [3], there are
infinitely many different choices of $N$, each producing a different graph
$G_{\ell}$. Therefore, if we can show that $(G_{\ell},T_{\ell})$ obtained from
a particular $N$ is a counterexample, then this implies an infinite class of
counterexamples.

Recall that $T_{\ell}$ is $3k$-edge-connected in $G_{\ell}$. Assuming that
$G_{\ell}$ admits $k$ edge-disjoint $T_{\ell}$-connectors, let
$Q_{1},\dots,Q_{k}$ be $T_{\ell}$-connectors obtained using Lemma 4.2, and let
$Q$ be their union.

Let us first assume that $\ell=0$ and therefore $k=1$, so the construction of
Section 3 is much simplified, as described at the end of that section. In this
case, we have $Q=Q_{1}$, where $Q_{1}$ is a $T_{0}$-connector. By Lemma 4.2
and Observation 4.1, $Q$ contains exactly two edges in each set
$\partial_{G_{0}}({X})$, where $X$ is an atom. By contracting each atom to a
vertex (reversing step 6 of the construction), we thus change $Q$ to a
$2$-regular spanning subgraph of $N$; since $Q$ is connected, it is a Hamilton
cycle of $N$, contradicting the choice of $N$.

In the rest of the proof, we assume that $\ell\geq 1$. We start by proving
that certain edge-cuts in the graphs $(F_{i},T_{i})$ correspond to basic edge-
cuts in $(G_{\ell},T_{\ell})$. Let $\widehat{F}$ be any specific copy of
$F^{*}_{i}$ (with the root deleted and atoms inserted at each remaining
terminal) in $G_{\ell}$. If $X$ is a set of vertices of $F_{i}$, then
$\partial_{F_{i}}({X})$ does not exist in $G_{\ell}$ because of the insertions
in steps 3 and 6 of the construction of $G_{\ell}$ in Section 3. On the other
hand, there is a well-defined set of edges of $G_{\ell}$ corresponding to
$\partial_{F_{i}}({X})$ in $\widehat{F}$, which we will denote by $\delta(X)$.
(Strictly speaking, some of these edges will only have one endvertex in
$\widehat{F}$ if they correspond to edges incident with the root of $F_{i}$.)

We let $\varepsilon(X)$ denote the set of edges of $G_{\ell}$ corresponding,
in the same fashion, to the edges of the induced subgraph $F_{i}[X]$ on $X$.
It will also be convenient to define

$\delta_{Q}(X)=\delta(X)\cap E(Q)\text{\quad
and\quad}\varepsilon_{Q}(X)=\varepsilon(X)\cap E(Q).$

In case that $X$ contains only one or two vertices, we omit the set brackets
in these expressions, writing just $\delta(v)$ or $\varepsilon_{Q}(v,w)$.

######  Claim 1.

Let $z$ be any terminal of $F_{i}$ (where $0\leq i\leq\ell-1$). Then
$\delta(z)$ (as defined for the specific copy $\widehat{F}$ of $F^{*}_{i}$) is
a basic edge-cut in $G_{\ell}$.

The claim is easy for a terminal $z$ such as $u^{A}_{1}$ or $v_{1}$, where the
only insertion during the construction of $G_{\ell}$ is in step 6 of the
construction of $G_{\ell}$, namely the insertion of a $K_{3,3k}$ at $z$,
creating an atom $X$. Now $\delta(z)=\partial_{G_{\ell}}({X})$, and by
Observation 4.1, $\partial_{G_{\ell}}({X})$ is basic.

This leaves only two cases to discuss: $f_{1}$ (and $f_{2}$, which is
symmetric), and the root terminal $r$ of $F_{i}$. Suppose first that $z=r$. In
the definition of basic edge-cut, choose $X_{0}$ as the set of all $3k$ non-
terminals of $\widehat{F}$ corresponding to the non-terminals in $F_{i}$; it
is easy to check that the requirements are fulfilled.

Suppose next that $z=f_{1}$. If $i=0$, then the situation is similar as for
$u^{A}_{1}$ above (the only insertion at $z$ creates an atom). Suppose that
$i>0$ consider the insertion of a copy of $F^{*}_{i-1}$ at $f_{1}$ in step 3.
Let $r^{\prime}$ denote the root of $F_{i-1}$, and define $\delta(r^{\prime})$
as above, with respect to this insertion. Then
$\delta(f_{1})=\delta(r^{\prime})$, which reduces the problem to the preceding
situation. The case $z=f_{2}$ is symmetric.

######  Claim 2.

Let $i\in[\ell-1]$ and let $\widehat{F}$ be a copy of $F^{*}_{i}$ (with the
root $r$ deleted and atoms inserted at each remaining terminal) in $G_{\ell}$.
Let $C$ be the set of all edges in $\partial_{G_{\ell}}({V(\widehat{F})})$
corresponding to output edges of $F_{i}$.Then

$C\subseteq Q\text{\quad or\quad}C\cap Q=\emptyset.$

We prove this claim by induction on $i$. It is vacuous for $i=0$, so let us
assume that $i>0$. We refer to Figure 1 for the notation.

By Claim 1 and property (i) of Lemma 4.2,

$|\delta_{Q}(v^{\prime}_{1})|=|\delta_{Q}(v^{\prime\prime}_{1})|=|\delta_{Q}(u^{B}_{1})|=2k.$
(3)

We want to show that

$\left|\varepsilon_{Q}(v^{\prime}_{1},v^{\prime\prime}_{1})\right|=k.$ (4)

Suppose that this is not the case and assume first that
$\left|\varepsilon_{Q}(v^{\prime}_{1},v^{\prime\prime}_{1})\right|<k$. Then
$\left|\varepsilon_{Q}(v^{\prime\prime}_{1},u^{B}_{1})\right|>k$ by (3), so
$|\delta_{Q}(u^{B}_{1})\setminus\varepsilon_{Q}(v^{\prime\prime}_{1},u^{B}_{1})|<k$
again by (3). Therefore,

$|\delta_{Q}(v^{\prime\prime}_{1},u^{B}_{1})|=|\varepsilon_{Q}(v^{\prime}_{1},v^{\prime\prime}_{1})|+|\delta_{Q}(u^{B}_{1})\setminus\varepsilon_{Q}(v^{\prime\prime}_{1},u^{B}_{1})|<2k,$

contradicting property (ii) of Lemma 4.2. It follows that
$\left|\varepsilon_{Q}(v^{\prime}_{1},v^{\prime\prime}_{1})\right|>k$. Then
$|\varepsilon_{Q}(v^{\prime\prime}_{1},u^{B}_{1})|<k$ and we obtain an
analogous contradiction for the set
$\delta_{Q}(v^{\prime}_{1},v^{\prime\prime}_{1})$. This proves (4).

Observe that the same argument proves (4) with $v^{\prime\prime}_{1}$ replaced
by any other terminal having only two neighbours in $F_{i}$ and with
$v^{\prime}_{1}$ replaced by any of these neighbours.

Next, we show

$|\delta_{Q}(f_{1})\setminus\delta_{Q}(u^{A}_{1},u^{B}_{1})|=|\delta_{Q}(u^{B}_{1})\setminus\delta_{Q}(f_{1},v^{\prime\prime}_{1})|.$
(5)

Indeed, $|\delta_{Q}(f_{1})|=|\delta_{Q}(u^{B}_{1})|=2k$ by Claim 1 and
property (i) of Lemma 4.2, and
$|\varepsilon_{Q}(f_{1},u^{A}_{1})|=|\varepsilon_{Q}(u^{B}_{1},v^{\prime\prime}_{1})|=k$
by the extension of (4) mentioned above. This implies that
$|\delta_{Q}(f_{1})\setminus\delta_{Q}(u^{A}_{1})|=|\delta_{Q}(u^{B}_{1})\setminus\delta_{Q}(v^{\prime\prime}_{1})|=k$,
and (5) follows since it just refers to removing the same subset
$\varepsilon_{Q}(f_{1},u^{B}_{1})$ from each of the sets in this equation.

Let us return to the inductive proof of Claim 2. By the induction hypothesis,
either all output edges of the copy of $F^{*}_{i-1}$ inserted at $f_{1}$ are
contained in $Q$, or none of them are. In other words,

$|\delta_{Q}(f_{1})\setminus\delta_{Q}(u^{A}_{1},u^{B}_{1})|\in\left\\{{0,2^{i-1}}\right\\}.$
(6)

Thus, the two sides of (5) sum up to $0$ or $2^{i}$. By the left-right
symmetry of Figure 1, all of the above works with the subscript $1$ replaced
by $2$; in particular, for $j=1,2$,

$|\delta_{Q}(f_{j})\setminus\delta_{Q}(u^{A}_{j},u^{B}_{j})|+|\delta_{Q}(u^{B}_{j})\setminus\delta_{Q}(f_{j},v^{\prime\prime}_{j})|\in\left\\{{0,2^{i}}\right\\}.$
(7)

Observe that if we know the value of the left hand side of (7) for $j=1,2$, we
can infer the number of edges in $C\cap Q$. This is because $Q$ has degree $0$
or $2$ on every non-terminal of $G_{\ell}$. Thus, an edge $e\in C$ is
contained in $Q$ if and only if exactly one of the two edges incident with $e$
at the non-terminal vertex is contained in $Q$. In particular, (7) implies
that the number of edges in $C\cap Q$ is either $0$ or $2^{i}$ as claimed.

A similar statement can be derived for the graph $F_{\ell}^{*}$.

######  Claim 3.

Let $\widehat{F}$ be a copy of $F^{*}_{\ell}$ (with the root $r$ deleted and
atoms inserted at each remaining terminal) in $G_{\ell}$. Given $p,q$, where
$1\leq p<q\leq 3$, let
$C=\varepsilon_{Q}(r,f_{pq})\cup\varepsilon_{Q}(r,f_{qp})$ (where $r$,
$f_{pq}$ and $f_{qp}$ are vertices of $F_{\ell}$, see Figure 2). Then

$C\subseteq Q\text{\quad or\quad}C\cap Q=\emptyset.$

For simplicity, let us consider the case $(p,q)=(1,2)$. Similarly to (3), we
can show that
$|\delta_{Q}(w_{1})|=|\delta_{Q}(f_{12})|=|\delta_{Q}(f_{21})|=2k$.
Furthermore,
$|\varepsilon_{Q}(w_{1},f_{12})|=|\varepsilon_{Q}(w_{2},f_{21})|=k$ is proved
analogously to (4). By combining these facts, we infer that

$|\varepsilon_{Q}(r,f_{12})|=|\varepsilon_{Q}(r,f_{21})|.$ (8)

We know from Claim 2 (applied to the copies of $F^{*}_{\ell-1}$ inserted at
$f_{12}$ and $f_{21}$, respectively) that the set on the left hand side of (8)
is empty or contains all edges of $G_{\ell}$ in $\varepsilon(r,f_{12})$. Thus,
the present claim follows from (8) and symmetry.

We have proved that for each $p,q$, where $1\leq p<q\leq 3$, $Q$ contains $0$
or $k$ edges in $\varepsilon_{Q}(r,f_{pq})\cup\varepsilon_{Q}(r,f_{qp})$.
Recall that this set of edges corresponds to a single edge $e=xy$ of the cubic
bipartite graph $N$ used in step 5 of the construction of $G_{\ell}$ (where
$x\in X$ is a vertex corresponding to the given copy of $F^{*}_{\ell}$ in
$G_{\ell}$, and $y\in Y$ corresponds to an independent set of $k$ non-
terminals in $G_{\ell}$). Since $Q$ either contains all edges of $G_{\ell}$
corresponding to $e$ or none (for each $e$) we can associate with $Q$ a
subgraph $Q_{N}$ of $N$. This subgraph is obtained from $Q$ by identification
of vertices, so $Q_{N}$ is a connected spanning subgraph of $N$.

We will prove that $Q_{N}$ is $2$-regular. We claim that the edge-cut
$\partial_{G_{\ell}}({V(\widehat{F})})$ is basic. To see this, recall that
uses a cubic graph $N$ with colour classes $X$ and $Y$; let $X_{0}$ be the set
of all non-terminals of $G_{\ell}$ coming from the vertices in $Y$, and check
that the said edge-cut is basic for $X_{0}$.

Lemma 4.2 therefore implies that $Q$ contains exactly $2k$ edges of
$\partial_{G_{\ell}}({V(\widehat{F})})$, and since $\widehat{F}$ is arbitrary,
$Q_{N}$ is $2$-regular. Being connected and spanning in $N$ at the same time,
$Q_{N}$ is a Hamilton cycle of $N$. This contradicts the choice of $N$ and
finishes the proof of Theorem 1.2. ∎

##  6 The case of even $k$

In this section, we outline the changes that need to be made when $k$ is an
arbitrary even positive integer (not necessarily a power of two). Define

$\ell=\lceil\log_{2}k\rceil\text{\quad and \quad}x=2^{\ell-1}-\frac{k}{2}.$

(In the preceding situation where $k$ is a power of two, the definition of
$\ell$ is consistent and $x$ is zero.) Note that $2^{\ell-1}<k\leq 2^{\ell}$
and consequently $0\leq x<\frac{k}{2}$.

We are constructing a graph with terminals $(G,T)$, where $T$ is $3k$-edge-
connected in $G$ and no $3k$ edge-disjoint $T$-connectors exist.

Steps 1–3 of the construction in Section 3 are carried out with a single minor
change: if $k$ is not divisible by $4$, then the multiplicities $\frac{3}{4}k$
and $\frac{3}{4}k-2^{i-1}$ appearing in the graph with terminals
$(F_{i},T_{i})$ in Figure 1 (each twice), have to be rounded. We do this in
such a way that the vertex $v_{1}$ of $F_{i}$ is adjacent to
$\lceil\frac{3}{4}k\rceil$ non-terminals incident with class $A$ edges and to
$\lfloor\frac{3}{4}k-2^{i-1}\rfloor$ non-terminals incident with class $B$
edges, and the rounding is performed in the opposite way for the non-terminals
adjacent to $v^{\prime}_{1}$. In particular, the number of class $A$ (class
$B$) edges of $F_{i}$ is $\frac{3}{2}k$ ($\frac{3}{2}k-2^{i}$, respectively),
and each of $v_{1},v^{\prime}_{1},v_{2}$ and $v^{\prime}_{2}$ has degree
exactly $3k$ in $F_{i}$ as required.

As a result, we have the graph $F^{*}_{\ell-1}$ with terminals
$T^{*}_{\ell-1}$ at our disposal. The number of class $C$ edges incident with
the root in this graph (cf. Figure 1 for a picture of $F_{\ell-1}$ is

$2(2^{\ell-1-1})=2^{\ell-1}=\frac{k}{2}+x.$

Furthermore, the number of class $A$ and $B$ edges is $\frac{3k}{2}$ and
$k-x$, respectively.

In step 4 of the construction, we use the graph $(F_{\ell},T_{\ell})$ as
before, with edge multiplicities as shown in Figure 2 (namely $\frac{k}{2}$,
$\frac{3k}{2}$ and $k$, respectively). We need to be careful when inserting
copies of $F^{*}_{\ell-1}$ at each vertex $f_{pq}$, where $1\leq p<q\leq 3$:
while the number of class $A$ edges in $F^{*}_{\ell-1}$ is right (namely
$\frac{3k}{2}$), there are too few class $B$ edges and too many class $C$
edges. Let us say we are inserting $F^{*}_{\ell-1}$ at $f_{12}$. We single out
a set $X$ of $x$ class $C$ edges (incident with the root $r$) in the given
copy of $F^{*}_{\ell-1}$, and perform the insertion using a bijection $h$
satisfying the following properties:

  * •

$h$ maps the edges incident with the root $r$ of $F_{\ell}$ to the edges
incident with the root of $F^{*}_{\ell-1}$ (of class $A$, $B$ or $C$),

  * •

$h$ maps the $\frac{3k}{2}$ edges between $r$ and $f_{12}$ to the class $A$
edges of $F^{*}_{\ell-1}$,

  * •

$h$ maps the $k$ edges between $f_{12}$ and $f_{21}$ to the class $B$ edges of
$F^{*}_{\ell-1}$ together with the class $C$ edges in $X$,

  * •

$h$ maps the $\frac{k}{2}$ edges between $f_{12}$ and $w_{1}$ to the class $C$
edges of $F^{*}_{\ell-1}$ not in $X$.

The same procedure is performed for each of the sets $f_{pq}$ in turn.

Steps 5–6 are copied verbatim, except that the resulting graph with terminals
is denoted by $(G,T)$ rather than $(G_{\ell},T_{\ell})$. Note that the
analogue of Observation 3.1 applies, and the subsequent proof goes through
essentially without change.

## References

  * [1] G. Brinkmann, J. Goedgebeur and B. D. McKay, The minimality of the Georges–Kelmans graph, _Mathematics of Computation_ 91 (2022), 1483–1500.
  * [2] M. DeVos, J. McDonald and I. Pivotto, Packing Steiner trees, _Journal of Combinatorial Theory, Series B_ 119 (2016), 178–213.
  * [3] M. N. Ellingham and J. D. Horton, Non-hamiltonian 3-connected cubic bipartite graphs, _Journal of Combinatorial Theory, Series B_ 34 (1983), 350–353.
  * [4] M. Kriesell, Edge-disjoint trees containing some given vertices in a graph, _Journal of Combinatorial Theory, Series B_ 88 (2003), 53–65.
  * [5] L. C. Lau, An approximate max-Steiner-tree-packing min-Steiner-cut theorem, _Combinatorica_ 27 (2007), 71–90.
  * [6] D. B. West and H. Wu, Packing of Steiner trees and $S$-connectors in graphs, _Journal of Combinatorial Theory, Series B_ 102 (2012), 186–205.