# Minimum Spanning Tree Cycle Intersection Problem

Manuel Dubinsky  Ingeniería Informática
Dpto. Tecnología y Administración
Universidad Nacional de Avellaneda
Argentina  César Massri  Dpto. de Matemática
Universidad de CAECE,
IMAS, CONICET
Argentina  Gabriel Taubin  School of Engineering,
Brown University,
USA

###### Abstract

Consider a connected graph $G$ and let $T$ be a spanning tree of $G$. Every
edge $e\in G-T$ induces a cycle in $T\cup\\{e\\}$. The intersection of two
distinct such cycles is the set of edges of $T$ that belong to both cycles. We
consider the problem of finding a spanning tree that has the least number of
such non-empty intersections.

##  1 Introduction

In this article we present what we believe is a novel problem in graph theory,
namely the Minimum Spanning Tree Cycle Intersection (_MSTCI_) problem.

The problem can be expressed as follows. Let $G$ be a graph and $T$ a spanning
tree of $G$. Every edge $e\in G-T$ induces a cycle in $T\cup\\{e\\}$. The
intersection of two distinct such cycles is the set of edges of $T$ that
belong to both cycles. Consider the problem of finding a spanning tree that
has the least number of such pairwise non-empty intersections.

The problem arose while investigating a (yet unpublished) method for _mesh
deformation_ in the area of _digital geometry processing_ , see [Botsch,
2010]. The method requires to solve a linear system and the sparsity of the
matrix is related to the solution of this problem.

The remaining of this section is dedicated to express the MSTCI problem in the
context of well established theories to motivate other points of view. Section
2 sets some notation and convenient definitions. In Section 3 the complete
graph case is analyzed. Section 4 presents a variety of interesting
properties, and a conjecture in the slightly general case of a graph (not
necessarily complete) that admits a star spanning tree. Section 5 explores
programatically the space of spanning trees to provide evidence that the
conjecture is well posed. Section 6 collects the conclusions of the article.

###  1.1 Intersection graph theory

_Intersection graph theory_ is a longstanding and central area of graph theory
covered in important textbooks [McKee and McMorris, 1999]. It is concerned
with the study of _intersection graphs_.

Let $\mathscr{F}=\\{S_{1},\dots,S_{k}\\}$ be any family of sets. The
_intersection graph_ denoted $\Omega(\mathscr{F})$ is the graph having
$\mathscr{F}$ as vertex set with $S_{i}$ adjacent $S_{j}$ if and only if
$i\neq j$ and $S_{i}\cap S_{j}\neq\varnothing$.

Let $G=(V,E)$ be a graph and $\mathscr{F}=\\{S_{1},\dots,S_{k}\\}$ be the
family of edge sets corresponding to the cycles of $G$. Then
$\Omega(\mathscr{F})$ has as vertex set the cycles of $G$ and two vertices are
adjacent if the corresponding cycles share at least one edge. In this setting,
let $T$ be a spanning tree of $G$ and $G-T\subset E$ the set of complementary
edges of $T$. An edge $e\in G-T$ induces a cycle in $T\cup\\{e\\}$ which
obviously is a cycle of $G$. So $T$ has a canonical mapping to some subgraph
of $\Omega(\mathscr{F})$. The MSTCI problem can be expressed in the following
terms: find the spanning tree $T$ such that it maps to the sparsest possible
subgraph in $\Omega(\mathscr{F})$.

###  1.2 Matroid theory

The classical _matroid theory_ as developed by Tutte in [Tutte, 1965] is a
fundamental theoretical toolbox with very deep insights in graph theory.

The familiy of sets described in the previous subsection closely resembles the
_polygon matroid_. An interesting formulation of the MSTCI problem can be
expressed in terms of its dual matroid $B(G)$, namely the _bond matroid_.

The bond matroid can be defined as follows. Let $G=(V,E)$ be a connected
graph. The _atoms_ of $B(G)$ are the edge subsets $A\subset E$ such that $G-A$
determine two connected components $G_{1}$ and $G_{2}$ and such that every
edge of $A$ has one end in each component.

A _dendroid_ $D$ of a matroid $M$ is a set that intersects all the atoms and
is minimal, meaning that if we delete an element of $D$ then there exists an
atom $A\in M$ such that $A\cap D=\varnothing$. The dendroids of $B(G)$ are the
sets of edges of the spanning trees of $G$.

Let $T$ be a spanning tree of $G$. So the edges of $T$ define a dendroid $D$
of $B(G)$. Note that for every edge $e\in T$, $T-\\{e\\}$ determine two
subtrees that span two connected components $G_{1}$ and $G_{2}$ of $G$. So
there is a natural injective map between the edges of $T$ and the atoms of
$B(G)$:

$\phi_{T}:E(T)\rightarrow B(G)$ $e\mapsto A$

where $A$ is the atom corresponding to the set of edges linking $G_{1}$ and
$G_{2}$. As a remark, note that $e\in A$. In the language of matroid theory
this set of $|V|-1$ atoms (ie. the image of $\phi_{T}$) of $B(G)$ is called
the _dendroid basis_ determined by $D$.

To formulate the MSTCI problem in this framework we have to be precise about
the pairwise intersection of cycles. In this sense let $T$ be a spanning tree
of a connected graph $G=(V,E)$. Let $S$ be the dendroid basis determined by
the edges of $T$ and $A\in S$ an atom. Clearly there exist a unique edge $e\in
T$ such that $\phi_{T}(e)=A$. Note that each edge $e^{\prime}\in A-\\{e\\}$
determine a cycle $c\in T\cup\\{e^{\prime}\\}$ and that $e\in c$. So two such
cycles have non-empty intersection. It is not difficult to realize that every
non-empty pairwise intersection is of this form. If we manage to count the set
of this pair of edges of all the atoms of $S$ we could express the MSTCI
problem as an alternative minimization problem: find the spanning tree such
that its corresponding dendroid basis has the least number of such pair of
edges.

###  1.3 Homology theory

The importance of _homological methods_ [Cartan, 1956] in topology and
geometry cannot be overemphasized. These methods constitute fundamental
algebraic tools that enable the computation of invariant quantities of spaces.
In its original form the main invariant was the number of “holes” of a space
known as its _Betti numbers_.

We introduce some elementary notions based these notes [Dewan, 2010]. Let $R$
be a commutative ring, and suppose we have a sequence of $R$-modules $M_{i}$
and homomorphisms $d_{i}$

$\dots\xrightarrow{d_{3}}M_{2}\xrightarrow{d_{2}}M_{1}\xrightarrow{d_{1}}M_{0}\xrightarrow{d_{0}}M_{-1}\xrightarrow{d_{-1}}\dots$

such that $\forall i\ d_{i}\circ d_{i+1}=0$. Such a sequence is called a
_chain complex_ of $R$-modules, and denoted $M_{\bullet}$. Because the
composition of adjacent homomorphisms is trivial, $im(d_{i+1})\subseteq
ker(d_{i})$. Therefore, for each module in the chain there is a quotient

$H_{i}(M_{\bullet})=\frac{ker(d_{i})}{im(d_{i+1})}$

called the _i-th homology group_ of $M_{\bullet}$.

In graph theory this definitions become very concrete. Let $R$ be a _principal
ideal domain_ (ie. $\mathbb{Z}$) and let $G=(V,E)$ be a graph. Consider an
arbitrary orientation of the edges that maps every edge $e\in E$ to a triple:
$e\mapsto(e,s,t)$, where $s,t\in V$ are the source and target ends of the
orientation of $e$. Let $M_{0}$ be the free $R$-module over $V$ (formal linear
combinations of the vertices of $G$). And $M_{1}$ the $R$-module generated by
the oriented edges subject to the relations $(e,s,t)+(e,t,s)=0$ (where
$(e,t,s)$ expresses de traversal of the edge $(e,s,t)$ in the opposite
direction). Now consider the _boundary homomorphism_

$\partial:M_{1}\rightarrow M_{0}$

defined on the generators as $\partial(e,s,t)=t-s$. Not surprisingly
$ker(\partial)$ is denoted the _cycle space_ of $G$, $\mathscr{C}(G)$. Since
if we consider in $M_{1}$ the linear combination representing a cycle $c$ of
$G$ then $\partial(c)=0$. It is not difficult to check that
$rank(\mathscr{C}(G))=|E|-|V|+c$ where $c$ is the number of connected
components of $G$. Now we can define the following chain complex
$G_{\bullet}$:

$\dots\xrightarrow{d_{3}=0}0\xrightarrow{d_{2}=0}M_{1}\xrightarrow{d_{1}=\partial}M_{0}\xrightarrow{d_{0}=0}0\xrightarrow{d_{-1}=0}\dots$

As $im(d_{2})=0$ then $H_{1}(G_{\bullet})=ker(\partial)=\mathscr{C}(G)$.

An interesting result is the following. Let $T$ be a spanning tree of $G$.
Note that if $e\in G-T$ then $T\cup{e}$ has only one cycle: $c_{e}$. The set
of those cycles generate $\mathscr{C}(G)$. Symbolically:

$<\\{c_{e}\ \forall e\in G-T\\}>=\mathscr{C}(G)=H_{1}(G_{\bullet})$

In other words: each spanning tree determines some basis of
$H_{1}(G_{\bullet})$. In particular if $T$ is a spanning tree that is a
solution of the MSTCI problem then the _tree intersection number_ (defined in
the next section) of $T$ could be a finer invariant of $G$.

##  2 Preliminaries

###  2.1 Overview

In the first part of this section we present some of the terms that are used
in the article. Then we define the notion of _closest-point_ and _closest-
point-set_. Finally we show a convenient cycle partition.

###  2.2 Notation

Let $G=(V,E)$ be a graph and $T$ a spanning tree of $G$, then we will refer to
the edges $e\in T$ as _tree-edges_ and to the edges $e\in G-T$ as _cycle-
edges_.

Every cycle-edge $e$ induces a cycle in $T\cup\\{e\\}$, we will call such a
cycle a _tree-cycle_. And we shall call $C_{T}$ to the set of tree-cycles of
$T$.

The intersection of two tree-cycles is the set of edges of $T$ that belong to
both cycles. We will define three functions concerning the intersection of
tree-cycles.

The first is $\cap_{T}(\cdot,\cdot):C_{T}\times C_{T}\rightarrow\\{0,1\\}$

$\cap_{T}(c_{i},c_{j}):=\begin{cases}1&c_{i}\cap c_{j}\neq\varnothing\land
c_{i}\neq c_{j}\\\ 0&c_{i}\cap c_{j}=\varnothing\lor c_{i}=c_{j}\\\
\end{cases}$

Note that the trivial case $c_{i}=c_{j}$ is excluded. This arbitrary decision
will simplify future computations.

The second is $\cap_{T}(\cdot):C_{T}\rightarrow\mathbb{N}$

$\cap_{T}(c_{i}):=\sum_{c_{j}\in C_{T}}\cap_{T}(c_{i},c_{j})$

We will call $\cap_{T}(c)$ the _cycle intersection number_ of $c$. Given a
tree-cycle $c$ we will denote $\cap_{T,c}$ as the set of tree-cycles that have
non-empty intersection with $c$. More precisely:

$\cap_{T,c}\equiv\\{c^{\prime}\in C_{T}:\cap_{T}(c,c^{\prime})=1\\}$

Note that $|\cap_{T,c}|=\cap_{T}(c)$.

To define the third function consider $\mathscr{T}_{G}$ to be the set of
spanning trees of $G$, so the definition will be as follows:
$\cap_{G}:\mathscr{T}_{G}\rightarrow\mathbb{N}$

$\cap_{G}(T):=\frac{1}{2}\sum_{c\in C_{T}}\cap_{T}(c)$

We will call $\cap_{G}(T)$ the _tree intersection number_ of $T$. Clearly the
set $\displaystyle\min_{T}\cap_{G}(T)$ is the set of solutions of the MSTCI
problem. If the graph is clear from the context we could drop the subindex and
simply write: $\cap(T)$.

We shall call _star_ spanning tree to a spanning tree that has one vertex that
connects to all other vertices. And $K_{n}$ to the complete graph on $n$
nodes. If $G=(V,E)$ we will say that $|V|=n$ is the number of vertices of $G$,
$|c|=k$ is the length of the cycle $c$ and $|p|$ is the length of the path
$p$. Also $uTv$ will denote the unique path between $u,v\in V$ in the spanning
tree $T$; $d_{T}(v)$ will be the degree of $v\in V$ relative to the spanning
tree $T$. We will denote $N(v)$ to the set of neighbor nodes of $v\in V$.

Finally we use the terms “node” and “vertex” interchangeably.

###  2.3 Closest point

In this section we prove the following simple fact: if $G=(V,E)$ is a
connected graph, $T$ a spanning tree of $G$ and $c\in C_{T}$ a tree-cycle,
then for every node $v\in V$ there exists a unique node $w\in c$ that
minimizes the distance to $v$ in $T$. We shall denote that node $closest-
point(v,c)$.

###### Lemma 1

Let $G=(V,E)$ be a connected graph, $T$ a spanning tree of $G$ and $c\in
C_{T}$ a tree-cycle then for every node $v\in V$ there exists a unique node
$w\in c$ such that

$|vTw|\leq|vTu|\ \forall u\in c$

Proof. The proof proceeds by contradiction. If $v\in c$ it is obviously its
own unique closest point. Suppose that $v\notin c$ and that there are two
distinct nodes $w,w^{\prime}\in c$ such that $|vTw|=|vTw^{\prime}|\leq|vTu|\
\forall u\in c$. Obviously $w^{\prime}\notin vTw$ and $w\notin vTw^{\prime}$,
we conclude that $vTw\cup wTw^{\prime}\cup vTw^{\prime}$ determine a cycle in
$T$ which contradicts the fact that $T$ is a tree.$\square$

The uniqueness of the $closest-point(v,c)$ leads to the following definition.

###### Definition 2

Let $G=(V,E)$ be a connected graph, $T$ a spanning tree of $G$ and $c\in
C_{T}$ a tree-cycle, then the set of closest points to a node $w\in c$ is
defined as follows

$closest-point-set(u,c):=\\{v\in V-c:$ $closest-point(v,c)=u\\}$

###  2.4 Tree cycle intersection partition

Now we define a partition of the set $\cap_{T,c}$. More precisely, let $G$ be
a connected graph, $T$ a spanning tree of $G$ and $c\in C_{T}$ a tree-cycle.
As defined above the set $\cap_{T,c}$ is the set of tree-cycles that have non-
empty intersection with $c$.

Let us consider any tree-cycle $c^{\prime}\in\cap_{T,c}$ induced by a cycle-
edge $e=(v,w)$. In this setting we can define the following partition:

  * •

_Internal tree-cycles_ : $c^{\prime}$ is _internal_ if $v,w\in c$.

  * •

_External tree-cycles_ : $c^{\prime}$ is _external_ if $v\notin c$ and $w\in
c$.

  * •

_Transit tree-cycles_ : $c^{\prime}$ is _transit_ if $v,w\notin c$.

Let us denote them $\cap^{i}_{T,c}$, $\cap^{e}_{T,c}$, $\cap^{t}_{T,c}$,
respectively. This partition will be convenient to simplify the computation of
the _intersection number_ of $c$.

##  3 Tree cycles of complete graphs

###  3.1 Overview

In this section we analyze the complete graph case $G=K_{n}$. First we deduce
a formula to compute the cycle intersection number. Then we prove that the
tree-cycles of a star spanning tree achieve the minimum cycle intersection
number. Finally we conclude that the star spanning trees are the unique
solutions of the MSTCI problem.

###  3.2 Cycle intersection number formula

In this subsection we consider the problem of finding a formula to count tree-
cycle intersections. More precisely, let $G=K_{n}$, $T$ a spanning tree of $G$
and $c$ a tree-cycle, we intend to derive a formula to calculate
$\cap_{T}(c)$.

The idea behind the formula is to consider the partition of $\cap_{T,c}$,
defined in the previous section. And then by combinatorial arguments compute
the number of elements in each class.

We shall analyze in turn the three classes: $\cap^{i}_{T,c}$,
$\cap^{e}_{T,c}$, $\cap^{t}_{T,c}$. In this section we will consider
$c^{\prime}\in\cap_{T}(c)$ to be a tree-cycle induced by a cycle-edge
$e=(v,w)$.

The simplest case is the internal tree-cycles class: $\cap^{i}_{T,c}$. Let
$c^{\prime}$ be an internal tree-cycle. By definition the nodes $v$ and $w$
belong to $c$, so the following holds: $(c^{\prime}\cap T)\subset c$ because
there is a unique path from $v$ to $w$ in $T$. So basically counting the
number of internal tree-cycles reduces to count the pairings of the nodes of
$c$ excluding some obvious cases. The cases that should be excluded are: the
pairing of a node with itself and with its neighbors in $c$. Then the number
of internal tree-cycles is:

$|\cap^{i}_{T,c}|=\frac{(k-3)k}{2},$

where $k$ is, as before, equal to $|c|$. The quotient is obviously due to the
fact that every cycle is counted twice.

Next we consider the class of external tree-cycles. Now let $c^{\prime}$ be an
external tree-cycle. In this case exactly one of the extremal nodes ($v$ or
$w$) belong to $c$. Without loss of generality (as we are considering
undirected edges), suppose that $v\notin c$ and $w\in c$. Clearly $w\neq
closest-point(v,c)$ because in that case $c^{\prime}\cap c=\varnothing$ and
consequently $c^{\prime}\notin\cap_{T,c}$ which contradicts our hypothesis. As
that is the only particular case that should be excluded, the number of
external tree-cycles is:

$|\cap^{e}_{T,c}|=(n-k)(k-1),$

where $n=|V|$ is the number of vertices of $G$ and $k=|c|$ is the length of
$c$.

Last we consider the class of transit tree-cycles. In this case the key
observation depends on the $closest-point-set$ definition of the previous
section. Lets define two classes of cycle-edges:

  1. 1.

A cycle-edge $e=(v,w)$ is called _intraset cycle-edge_ if both $v,w\in
closest-point-set(u_{i},c)$ for some $u_{i}\in c$

  2. 2.

A cycle-edge $e=(v,w)$ is called _interset cycle-edge_ if $v\in closest-point-
set(u_{i},c)$ and $w\in closest-point-set(u_{j},c)$ where $u_{i},u_{j}\in c$
and $u_{i}\neq u_{j}$

Then:

  * •

Every _intraset cycle-edge_ induce a tree-cycle $c^{\prime}$ such that
$c^{\prime}\cap c=\varnothing$

  * •

Every _interset cycle-edge_ induce a tree-cycle $c^{\prime}$ such that
$c^{\prime}\cap c\neq\varnothing$

So we should consider _interset cycle-edges_ or equivalently, the pairing of
the nodes that are in different sets. Let $q_{i}=|closest-point-set(w_{i},c)|$
be defined for all $w_{i}\in c$, then the number of transit tree-cycles is:

$|\cap^{t}_{T,c}|=\sum_{i<j}q_{i}q_{j}=\frac{1}{2}\sum_{i=1}^{k}q_{i}(n-k-
q_{i})$

Finally, the intersection number formula is the aggregation of the three
classes:

$\cap_{T}(c)=|\cap_{T,c}|=|\cap^{i}_{T,c}|+|\cap^{e}_{T,c}|+|\cap^{t}_{T,c}|=$

$\frac{(k-3)k}{2}+(n-k)(k-1)+\frac{1}{2}\sum_{i=1}^{k}q_{i}(n-k-q_{i}),$

where $n$ is the number of vertices of $G$, $k=|c|$ and $q_{i}=|closest-point-
set(w_{i},c)|$ for $w_{i}\in c$.

###  3.3 Main result

In this subsection we start by defining _transiteless_ tree-cycles. Then we
prove two lemmas. The first shows that for every cycle $c\in G=K_{n}$ we can
build a spanning tree $T$ such that $c$ is a tree-cycle of $T$ and the
intersection number $\cap_{T}(c)$ is minimal. And the second calculates the
intersection number of tree-cycles of star spanning trees. Finally we prove
the main result of this section, namely that star spanning trees minimize
$\cap(\cdot)$ in the case of complete graphs.

###### Definition 3

Let $G=(V,E)$ be a connected graph, $T$ a spanning tree of $G$ and $c\in
C_{T}$ a tree-cycle, we call $c$ a _transitless_ tree-cycle if
$|\cap^{t}_{T,c}|=0$.

As an important remark, note that the number of elements in the internal and
external classes of $c$ are independent of the spanning tree because they
depend exclusively on the numbers $n=|V|$ and $k=|c|$. So two spanning trees
$T_{1}$ and $T_{2}$ that have $c$ as a tree-cycle induce an intersection
number (for $c$) that only differ in the number of elements in their transit
classes. We conclude that transitless tree-cycles have minimal intersection
number $\cap_{T}(c)$.

###### Lemma 4

Let $G=K_{n}$ and let $c$ be a cycle of $G$ then the following procedure lead
to a spanning tree $T$ that minimizes the intersection number of $c$:

  1. 1.

Remove exactly one edge $e\in c$

  2. 2.

Choose a vertex $v\in c$

  3. 3.

Define $T$ as follows:

     * •

The edges $c-e$

     * •

A star centered at $v$ of the vertices $(G-c)\cup\\{v\\}$

Proof. Note that $T$ is a spanning tree of $G$, and $c$ is a tree-cycle of
$T$. So if we prove that $|\cap^{t}_{T,c}|=0$ then the intersection number
$\cap_{T}(c)$ is minimal. This is the case, because by construction:

  * •

$|closest-point-set(u,c)|=0$ $\forall u\in c,u\neq v$

  * •

$|closest-point-set(v,c)|=n-k$

So $|\cap^{t}_{T,c}|=\sum_{i<j}q_{i}q_{j}=0$.$\square$

###### Lemma 5

Let $G=K_{n}$ and let $T_{s}$ be a star spanning tree of $G$. Then the the
following property holds

$\cap_{T_{s}}(c)=2(n-3)$

for any tree-cycle $c$ of $T_{s}$.

Proof. Clearly the tree-cycles in $T_{s}$ have the same intersection number
(by symmetry). Let $c$ be a tree-cycle of $T_{s}$. Note that $c$ is a triangle
($|c|=3$), so the corresponding internal tree-cycles class is empty:
$|\cap^{i}_{T,c}|=0$. Also note that $c$ is a transitless tree-cycle because
its nodes are: the central node and two leaf nodes of $T_{s}$. So the external
tree-cycle class is the only non-empty class:

$\cap_{T_{s}}(c)=|\cap^{e}_{T_{s},c}|=2(n-3)$

###### Proposition 6

Let $G=K_{n}$ and let $T_{s}$ be a star spanning tree of $G$. Then the
following property holds

$\cap_{T_{s}}(\cdot)\leq\cap_{T}(\cdot)$

where $T$ is any spanning tree of $G$.

Proof. We shall prove the proposition by contradiction. Suppose that a
spanning tree $T$ and a tree-cycle $c$ of $T$ exist such that:

$\cap_{T}(c)<\cap_{T_{s}}(\cdot)=2(n-3)$

We can assume that $c$ is transitless because, if it’s not the case, by lemma
4 we can build a spanning tree $T^{\prime}$ such that
$\cap_{T^{\prime}}(c)<\cap_{T}(c)$. In this context the inequality can be
expressed as

$\cap_{T}(c)=|\cap^{i}_{T,c}|+|\cap^{e}_{T,c}|=$
$\frac{(k-3)k}{2}+(n-k)(k-1)<2(n-3)$

Expanding and simplifying the expression we have

$\frac{-1}{2}k^{2}+(n-\frac{1}{2})k-3n+6<0$

The roots of this quadratic polynomial are: $r_{1}=3$ and $r_{2}=2(n-2)$. We
should consider two cases depending on the relation of the roots:

  1. 1.

$r_{1}<r_{2}$

  2. 2.

$r_{1}>r_{2}$

The case $r_{1}=r_{2}$ can be discarded because it leads to a fractional
number of nodes ($n=\frac{7}{2}$). In the first case the inequality holds for
$k<r_{1}=3$ or $k>r_{2}=2(n-2)$. The case $k<3$ is an obvious contradiction
since the size of the cycle must be $|c|=k\geq 3$. The case $k>2(n-2)$
combined with the fact that $k\leq n$ induces the following inequality

$r_{1}=3<r_{2}=2(n-2)<k\leq n$

which implies a contradiction: $3<n<4$, since $n$ is a positive integer.

The second case ($r_{1}=3>r_{2}=2(n-2)$) imply $n<\frac{7}{2}$. So the only
case that should be considered is $k=n=3$ since $k\leq n$. But, this
inequality is false because $k=3$ is a root of the quadratic
polynomial.$\square$

###### Corollary 7

Let $G=K_{n}$ and let $T_{s}$ be a star spanning tree of $G$. Then the the
following property holds

$\cap(T_{s})\leq\cap(T),$

where $T$ is any spanning tree of $G$.

Proof. As expressed by proposition 6, a tree-cycle of a star spanning tree has
the minimal intersection number among all tree-cycles. Since any tree-cycles
of a star spanning tree has the same intersection number, we conclude that the
tree intersection number of a star spanning tree $\cap(T_{s})$ is minimal
among all spanning trees. $\square$

This corollary can be further improved to a strict inequality. In other words:
star spanning trees are the unique minimizers of $\cap(T)$.

###### Corollary 8

Let $G=(V,E)=K_{n}$ where $|V|=n>4$ and let $T_{s}$ be a star spanning tree of
$G$. Then, the following property holds

$\cap(T_{s})<\cap(T),$

where $T$ is any non-star spanning tree of $G$.

Proof. A careful reading of proposition 6 leads to the conclusion that the
equality $\cap_{T_{s}}(c)=\cap_{T}(c)$ is achieved when $k$ is either
$r_{1}=3$ or $r_{2}=2(n-2)$ (the roots of the quadratic polynomial). If
$k=r_{2}=2(n-2)$, and taking into account that $3\leq k\leq n$, we conclude
that $\frac{7}{2}\leq n\leq 4$; this case is explicitly excluded from our
hypotheses (in fact, it is not difficult to check that the three non-
isomorphic spanning trees of $K_{4}$ all have the same tree intersection
number).

The other possibility is $k=r_{1}=3$. As all the tree-cycles of $T_{s}$ fall
into this category, it is enough to show that $T$ has a tree-cycle $c$ such
that $|c|=k>3$ to conclude our thesis. Let $w\in V$ be a node with maximum
degree in $T$. And let $d_{T}(w)$ denote the degree of $w$ in $T$ and $N(w)$
to the set of neighbors of $w$ in $T$. As $T$ is a non-star spanning tree then
$2\leq d_{T}(w)<n-1$. So there is a node $u\in V$ such that $u\notin N(w)$ in
$T$, and there is a node $k\in N(w)$ such that $k\notin wTu$. Notice that the
edge $e=(u,k)\notin T$ (since it would induce a cycle). Hence, it is a cycle-
edge. Note that the tree-cycle induced by $e$ has length at least 4.$\square$

This result can be summarized in the following way: star spanning trees are
the unique solutions of the MSTCI problem for complete graphs.

##  4 Further generalization

###  4.1 Overview

Now we explore some aspects of a slightly more general case, namely: the MSTCI
problem in the context of a graph (not necessarily complete) $G=(V,E)$ that
admits a star spanning tree $T_{s}$. In the first part we present a formula to
calculate $\cap(T_{s})$. In the second part we show that $\cap(T_{s})$ is a
local minimum in the domain of what we refer to as the “spanning tree graph”.
In the third part we prove a result that suggests a general observation: the
fact that a spanning tree of a graph $G$ being a solution of the MSTCI problem
doesn’t depend on an intrinsic property of $T$ but on the particular embedding
of $T$ in $G$. Finally we conjecture a generalization of Corollary 7:
$\cap(T_{s})\leq\cap(T)$ for every spanning tree $T$ of $G$.

###  4.2 Formulas for star spanning trees

In this subsection we present two formulas for graphs $G=(V,E)$ that admit a
star spanning tree $T_{s}$. Let us denote $v\in V$ to the central node of
$T_{s}$.

The first formula corresponds to the cycle intersection number of a tree-cycle
$c=(u,v,w)\in C_{T_{s}}$, namely $\cap_{T_{s}}(c)$. Recall from the previous
section that $c$ does not intersect neither transit nor internal tree-cycles:
$|\cap^{t}_{T,c}|=0$ and $|\cap^{i}_{T,c}|=0$. So its non-empty intersections
are the tree-cycles in the set $\cap^{e}_{T,c}$. Note that the remaining
incident edges to $u$ and $w$, are the only source of tree-cycles that have
non-empty intersection with $c$. So the formula is straightforward:

$\cap_{T_{s}}(c)=d(u)-2+d(w)-2,$

where $d(u)$ and $d(w)$ are the degrees of $u$ and $w$, resp.

Now we shall deduce a formula for the tree intersection number $\cap(T_{s})$.
Based on the preceding observations and the fact that each node $u\in
V-\\{v\\}$ is involved in $d(u)-1$ tree-cycles and for each of those tree-
cycles it produces $d(u)-2$ non-empty intersections (note that the pairwise
intersections are counted twice). The formula is as follows:

$\cap(T_{s})=\frac{1}{2}\sum_{u\in V-\\{v\\}}(d(u)-1)(d(u)-2)=$

$\frac{1}{2}\sum_{u\in V-\\{v\\}}d(u)^{2}-3d(u)+2$

If we denote ${\bf d}$ as the degree vector of $G$, that is: a vector that has
in the $i$-th component the degree of the $i$-th vertex. And taking into
account that $\sum_{u\in V}d(u)=2m$ where $m=|E|$, the formula can be
expressed as:

$\cap(T_{s})=\frac{1}{2}[||{\bf d}||_{2}^{2}-6m-(n-1)(n-6)]$

###  4.3 Star spanning tree as a local minimum

In this subsection we prove that a star spanning tree is a local minimum
respect to the tree intersection number in the domain of the _spanning tree
graph_. We start by defining this second order graph of the original graph
$G=(V,E)$. Then we analyze the structure of the neighbors of a star spanning
tree $T_{s}$. Finally we demonstrate the result by a bijection between tree-
cycles to conclude that $\cap(T_{s})$ is a local minimum.

###### Definition 9

Let $G=(V,E)$ be a graph, and $S$ a subgraph of $G$. We denote as
$e\leftrightarrow e^{\prime}$ to the operation of replacing the edge $e\in S$
with the edge $e^{\prime}\in G-S$. We call this operation _edge replacement on
$S$_.

###### Definition 10

Let $G=(V,E)$ be a graph. We denote $SP_{{}_{G}}$ to the graph that has one
node for every spanning tree of $G$ and an edge between two nodes if the
corresponding spanning trees differ in exactly one edge replacement. We call
this graph the _spanning tree graph of $G$_.

####  4.3.1 Neighborhood of $T_{s}$

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$ with $v\in
V$ as its center. Let $\alpha_{{}_{T_{s}}}$ be the node corresponding to
$T_{s}$ in $SP_{{}_{G}}$ and let $\alpha_{{}_{T}}$ (with corresponding
spanning tree $T$) be any neighbor of $\alpha_{{}_{T_{s}}}$. By definition
$T_{s}$ and $T$ differ in exactly one edge replacement $e\leftrightarrow
e^{\prime}$ where $e=(v,w)\in T_{s}$ and $e^{\prime}=(u,w)\in T$. Note that
$T$ is exactly the same as $T_{s}$ except that the node $w$ is no longer
connected to the central node $v$ but is connected to the intermediate node
$u$. This similar structure has direct consequences in the intersection
numbers of both trees.

Now we prove the result of this section.

###### Theorem 11

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$ with $v\in
V$ as its center. Then, $T_{s}$ is a local minimum respect to the tree
intersection number in the domain of $SP_{{}_{G}}$.

Proof. Let $T$ be a spanning tree corresponding to a neighbor of $T_{s}$ in
$SP_{{}_{G}}$. Then we want to prove that $\cap(T_{s})\leq\cap(T)$. We shall
proceed by defining a bijection between the tree-cycles of both trees
$\\{c\leftrightarrow d:c\in C_{{}_{T_{s}}}\wedge d\in C_{{}_{T}}\\}$ such that
$\cap_{{}_{T_{s}}}(c)\leq\cap_{{}_{T}}(d)$, this strategy clearly implies the
thesis since by definition:

$\cap(T_{s})=\frac{1}{2}\sum_{c}\cap_{T_{s}}(c)\leq\frac{1}{2}\sum_{d}\cap_{T}(d)=\cap(T)$

Let $e_{{}_{T_{s}}}\leftrightarrow e_{{}_{T}}$ with $e_{{}_{T_{s}}}=(v,w)\in
T_{s}$ and $e_{{}_{T}}=(u,w)\in T$ be the edge replacement in $SP_{{}_{G}}$.
Consider the following simple facts:

  * •

$e_{{}_{T}}$ is a cycle-edge in $T_{s}$, with corresponding tree-cycle $c$

  * •

$e_{{}_{T_{s}}}$ is a cycle-edge in $T$, with corresponding tree-cycle $d$

  * •

Except for $e_{{}_{T_{s}}}$ and $e_{{}_{T}}$, $T_{s}$ and $T$ have the same
set of cycle-edges. For every $e\in E-T_{s}-T$ we denote $c_{e}$ and $d_{e}$
to the corresponding tree-cycles in $T_{s}$ and $T$, resp.

according to this naming convention, we can define the following “natural”
bijection between tree-cyles:

$\\{c\leftrightarrow d\\}\cup\\{c_{e}\leftrightarrow d_{e}:e\in E-T_{s}-T\\}$

In order to compare the intersection numbers of the bijected pairs it is
convenient to distiguish the following partition:

  * •

Case 1: the pair induced by the edge replacement, $\\{c\leftrightarrow d\\}$

  * •

Case 2: pairs induced by cycle-edges non-incident to $u$ nor to $w$,
$\\{c_{e}\leftrightarrow d_{e}:e\in E-T_{s}-T\wedge u\notin e\wedge w\notin
e\\}$

  * •

Case 3: pairs induced by cycle-edges incident to $u$ or $w$,
$\\{c_{e}\leftrightarrow d_{e}:e\in E-T_{s}-T\wedge(u\in e\lor w\in e)\\}$

Case 1 is the easiest: note that $c$ and $d$ are the same tree-cycle
$(u,v,w)$, which is a transitless triangle, so its intersection number is
determined by its external intersections:

$\cap_{{}_{T_{s}}}(c)=d(u)-2+d(w)-2=\cap_{{}_{T}}(d)$

Case 2 is similar, let $e=(h,k)$ be a cycle-edge non-incident to $u$ or to $w$
and $c_{e}\leftrightarrow d_{e}$ its corresponding pair of bijected tree-
cycles. Clearly $e$ determines the transitless triangle $(h,v,k)$ both in
$T_{s}$ and $T$ and as
$d_{{}_{T_{s}}}(h)=d_{{}_{T_{s}}}(k)=d_{{}_{T}}(h)=d_{{}_{T}}(k)=1$, then
every other edge incident to $h$ or $k$ induces a tree-cycle that intersects
$(h,v,k)$. We conclude that:

$\cap_{{}_{T_{s}}}(c_{e})=d(h)-2+d(k)-2=\cap_{{}_{T}}(d_{e})$

Case 3 is the one that should be analyzed more carefully. As we already know
how to calculate intersection numbers of tree-cycles in $T_{s}$, we will focus
on the tree-cycles of $T$. We will further divide this partition in two
subpartitions:

  * •

Case 3.1: pairs induced by cycle-edges incident to $u$,
$\\{c_{e}\leftrightarrow d_{e}:e\in E-T_{s}-T\wedge u\in e\\}$

  * •

Case 3.2: pairs induced by cycle-edges incident to $w$,
$\\{c_{e}\leftrightarrow d_{e}:e\in E-T_{s}-T\wedge w\in e\\}$

In case 3.1 the situation is as follows: the cycle-edge $e=(u,k)$ defines the
tree-cycle $c_{e}=d_{e}=(u,v,k)$ (both in $T$ and $T_{s}$). The important
details are:

  * •

$d_{T}(u)=2$: $u$ induces $d(u)-3$ intersections

  * •

$d_{T}(k)=1$: $k$ induces $d(k)-2$ intersections

  * •

$d_{T}(w)=1$: $w$ induces $d(w)-1$ intersections

  * •

$d(w)\geq 2$ since it is connected at least to $u$ and $v$ in $G$

  * •

$w$ may have an incident cycle-edge connecting it to $k$, so we should avoid
counting twice that intersection

Now we claim that

$\cap_{{}_{T}}(d_{e})\geq d(u)-3+d(k)-2+d(w)-1-\epsilon(w,k)$ $\geq
d(u)-2+d(k)-2=\cap_{{}_{T_{s}}}(c_{e})$

where

$\epsilon(w,k)=\begin{cases}1&(w,k)\in E\\\ 0&otherwise\\\ \end{cases}$

The inequality follows since $d(w)-1-\epsilon(w,k)\geq 1$.

In case 3.2 the situation is as follows: the cycle-edge $e=(w,h)$ defines the
tree-cycle $d_{e}=(w,u,v,h)$ in $T$ and $c_{e}=(w,v,h)$ in $T_{s}$. The
important details are:

  * •

$d_{T}(u)=2$: $u$ induces $d(u)-2$ intersections

  * •

$d_{T}(h)=1$: $h$ induces $d(h)-2$ intersections

  * •

$d_{T}(w)=1$: $w$ induces $d(w)-2$ intersections

  * •

$u$ may have an incident cycle-edge connecting it to $h$, so we should avoid
counting twice that intersection

And we claim that

$\cap_{{}_{T}}(d_{e})\geq d(w)-2+d(h)-2+d(u)-2-\epsilon(u,h)$ $\geq
d(w)-2+d(h)-2=\cap_{{}_{T_{s}}}(c_{e})$

The inequality follows since $d(u)-2-\epsilon(u,h)\geq 0$.

$\square$

###  4.4 Intrinsic tree invariants

In this subsection we consider the following question: is there any
correlation between an _intrinsic tree invariant_ and the tree intersection
number of the spanning trees for every graph? If so we could formulate an
alternative characterization of the MSTCI problem expressed in terms of the
invariant.

By _intrinsic tree invariant_ we denote a map
$f:\mathscr{T}\rightarrow\mathbb{R}$ on the set of all trees. Of particular
interest are the degree-based topological indices [Gutman, 2013]. The
topological index that motivated our question is the _atom-bond connectivity_
(ABC) index [Estrada, 1998]. As shown by [Furtula, 2009] the star trees are
maximal among all trees respect to the ABC index. In the previous section we
proved that in the complete graph the star spanning trees are minimal respect
to the tree intersection number. Consequently we can formulate a natural
question: is there a negative correlation between the ABC index of the
spanning trees and their corresponding intersection numbers?

We will prove that the answer to our question is negative. Without loss of
generality we will consider positive correlation (negative correlation is
analogous). The underlying idea of the proof is as follows: suppose that there
exists an intrinsic tree invariant $f:\mathscr{T}\rightarrow\mathbb{R}$ such
that for every graph $G$ the intersection number $\cap(\cdot)$ is positively
correlated with $f$, this can be expressed as:

$f(T_{1})\leq f(T_{2})\iff\cap_{G}(T_{1})\leq\cap_{G}(T_{2}),\forall
G,T_{1},T_{2}$

According to this property if we consider two trees $T_{1}$ and $T_{2}$ and
two graphs $G$ and $H$ such that $T_{1},T_{2}\in\mathscr{T}_{G}$ and
$T_{1},T_{2}\in\mathscr{T}_{H}$, then this equivalence follows:

$\cap_{G}(T_{1})\leq\cap_{G}(T_{2})\iff\cap_{H}(T_{1})\leq\cap_{H}(T_{2})$

So it suffices to show that there exist $T_{1}$, $T_{2}$, $G$ and $H$ such
that the equivalence is not satisfied to answer the question negatively.

First we prove a simple lemma regarding the tree intersection number of a
spanning tree $T$ under the removal of a cycle-edge. Namely if a cycle-edge
$e$ is removed from $G$ then the tree intersection number of $T$ decreases
exactly in the intersection number of its corresponding tree-cycle.

###### Lemma 12

let $G=(V,E)$ be a graph, $T\in\mathscr{T}_{G}$ a spanning tree, $e\in G-T$ a
cycle-edge, and $c$ the corresponding tree-cycle, then the following holds:

$\cap_{G-e}(T)=\cap_{G}(T)-\cap_{T}(c)$

Proof. As the spanning tree $T$ is the same in both graphs: $G$ and $G-e$,
then the remaining cycle-edges define the same tree-cycles so their pairwise
intersection relations are identical. As $c$ is not a cycle in $G-e$ then the
equality follows. $\square$

###### Theorem 13

There is no intrinsic tree invariant $f:\mathscr{T}\rightarrow\mathbb{R}$
positively correlated with the intersection number $\cap_{G}(\cdot)$ for every
graph $G$.

Proof. We will proceed by contradiction: let $f$ be such an intrinsic tree
invariant. Then by definition for arbitrary graphs $G$ and $H$ the following
equivalences hold

$f(T_{1})\leq f(T_{2})\iff\cap_{G}(T_{1})\leq\cap_{G}(T_{2})$

$f(T_{1})\leq f(T_{2})\iff\cap_{H}(T_{1})\leq\cap_{H}(T_{2})$

Where $T_{1},T_{2}\in\mathscr{T}_{G}$ and $T_{1},T_{2}\in\mathscr{T}_{H}$.
This in turn imply that

$\cap_{G}(T_{1})\leq\cap_{G}(T_{2})\iff\cap_{H}(T_{1})\leq\cap_{H}(T_{2})$

The proof will be based on showing two graphs and two spanning trees such that
the latter equivalence is not valid.

  * •

Let $G$ be the complete graph $K_{n}$

  * •

Let $H$ be the graph $K_{n}-\\{e_{i,1},\dots,e_{i,n-3}\\}$ where the edges
$e_{i,1},\dots,e_{i,n-3}$ are $n-3$ edges incident to some arbitrary node
$v_{i}$. We will refer to $v_{i}$ as the _almost disconnected_ node of $H$.
Note that $d(v_{i})=2$.

  * •

Let $T_{1}$ be the star spanning tree $T_{s}$

  * •

Let $T_{2}$ be the spanning tree defined as
$T_{s}-\\{e_{i}\\}\cup\\{e_{i,j}\\}$, where $e_{i}$ is the edge that connects
some arbitrary node $v_{i}$ (in $H$ this role will be played by the almost
disconnected node) to the center of the star and $e_{i,j}$ is an edge that
connects $v_{i}$ to a different node $v_{j}$.

It is easy to check that $T_{1}$ and $T_{2}$ are spanning trees of both $G$
and $H$. If we also suppose that $|V|=n>4$ then by corollary 8

$\cap_{G}(T_{1})<\cap_{G}(T_{2})$

By the previous equivalence it is expected that
$\cap_{H}(T_{1})<\cap_{H}(T_{2})$ as well. But we will show that this is not
the case.

By a suitable labelling of the nodes of $H$ we can refer to: the center of the
star spanning tree as $v_{1}$, the almost disconnected node of $H$ as $v_{2}$
and the other neighbor of $v_{2}$ as $v_{3}$. By lemma 12 arises that

$\cap_{H}(T_{1})=\cap_{H-e_{{}_{2,3}}}(T_{1})+\cap_{T_{1}}(c_{{}_{2,3}})$

$\cap_{H}(T_{2})=\cap_{H-e_{{}_{1,2}}}(T_{2})+\cap_{T_{2}}(c_{{}_{1,2}})$

Where $c_{{}_{2,3}}$ and $c_{{}_{1,2}}$ are the tree-cycles induced by
$e_{{}_{2,3}}$ and $e_{{}_{1,2}}$ in $T_{1}$ and $T_{2}$, resp. Since the
remaining tree-cycles corresponding to both trees are the same then

$\cap_{H-e_{{}_{2,3}}}(T_{1})=\cap_{H-e_{{}_{1,2}}}(T_{2})$

And this imply the following

$\cap_{H}(T_{1})-\cap_{H}(T_{2})=\cap_{T_{1}}(c_{{}_{2,3}})-\cap_{T_{2}}(c_{{}_{1,2}})$

It is an easy exercise to check that

$\cap_{T_{1}}(c_{{}_{2,3}})=\cap_{T_{2}}(c_{{}_{1,2}})=d(v_{3})-2=n-3$

At this point we can conclude that

$\cap_{H}(T_{1})=\cap_{H}(T_{2})$

Contradicting the fact that $f$ is positively correlated with the tree
intersection number for every graph.$\square$

The underlying key fact of this result is that a spanning tree $T$ that solves
the the MSTCI problem for a graph $G$ does not depend on intrinsic properties
of $T$ but on the embedding of $T$ in $G$.

Note that as an interesting side effect this demonstration shows that a star
spanning tree is not necessarily a strict local minimum in the spanning tree
graph (see previous subsection).

###  4.5 Intersection number conjecture

In this subsection we present the conjecture $\cap(T_{s})\leq\cap(T)$ for
every spanning tree $T$ generalizing theorem 11. Then we explore two ideas to
simplify a hypothetical counterexample of the conjecture. The first is based
on the notion of _interbranch_ cycle-edge. We show that if a non-star spanning
tree $T$ exists such that $\cap(T)<\cap(T_{s})$, then the inequality must hold
if we remove the interbranch cycle-edges. The second is based on the notion of
_principal subtree_. In this case we show that the inequality must hold for
some principal subtree of $T$. This ideas will be of practical use in the next
section.

####  4.5.1 The conjecture statement

We present below the conjecture that generalizes the case of complete graphs.

###### Conjecture 14

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$, then

$\cap(T_{s})\leq\cap(T)$

for every spanning tree $T\in\mathscr{T}_{G}$.

As an important remark, a demonstration of this result seems difficult if
approached by a local-to-global strategy as in the complete graph case exposed
previously.

####  4.5.2 Counterexample simplification

In this part we consider some ideas to simplify a hypothetical counterexample
of conjecture 14.

Below we define the notion of _interbranch_ cycle-edge.

###### Definition 15

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$ and let
$v\in V$ be the center of $T_{s}$. Let $T\in\mathscr{T}_{G}$ be a spanning
tree. We call _interbranch cycle-edge of $T$_ to any cycle-edge of $T$,
$e=(u,w)$, such that $closest-point(v,c)\neq u,w$, where $c$ is the induced
tree-cycle of $e$ in $T$.

The intuition behind this definition is that the paths $vTu$ and $vTw$ belong
to different branches. Or equivalently, $u$ and $w$ are not collinear with
respect to $v$ in $T$. The following lemma shows that if we can find a
counterexample to the conjecture 14 (ie.: $\cap(T)<\cap(T_{s})$) then we can
build a simpler counterexample removing from $G$ the interbranch cycle-edges
of $T$.

###### Lemma 16

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$ with $v\in
V$ as its center. Let $T\in\mathscr{T}_{G}$ be a spanning tree such that
$\cap_{G}(T)<\cap_{G}(T_{s})$ and let $\Delta_{T}$ be the set of interbranch
cycle-edges of $T$, then

$\cap_{{}_{G-\Delta_{T}}}(T)<\cap_{{}_{G-\Delta_{T}}}(T_{s})$

Proof. Let $e=(u,w)\in\Delta_{T}$. Note that $e$ is also a cycle-edge in
$T_{s}$ since $v\neq u,w$ by definition of interbranch cycle-edge. So $e$
determines the tree-cycle $c$ in $T_{s}$ and the tree-cycle $c^{\prime}$ in
$T$. By the intersection number formula it arises that
$\cap_{{}_{T_{s}}}(c)=d(u)-2+d(w)-2$. On the other hand, since the other
neighbors of $u$ and $w$ are connected to $v$, they belong to distinct tree-
cycles with non-trivial intersection with respect to $c^{\prime}$ in $T$. We
conclude that

$\cap_{{}_{T}}(c^{\prime})\geq d(u)-2+d(w)-2=\cap_{T_{s}}(c).$

Hence by lemma 12,

$\displaystyle\cap_{G-e}(T)=$ $\displaystyle\cap_{G}(T)-\cap_{T}(c^{\prime})<$
$\displaystyle\cap_{G}(T_{s})-\cap_{T_{s}}(c)=\cap_{G-e}(T_{s})$

Applying the same procedure for every edge in $\Delta_{T}$, the claimed
inequality follows.$\square$

###### Definition 17

Let $T=(V,E)$ be a rooted tree graph with root $v\in V$. Let $w\in N(v)$ then
we call _principal subtree respect to w_ to the subtree spanned by $v$ and the
nodes $u\in V$ such that $w\in vTu$.

The next lemma expresses the intersection number of a spanning tree (without
interbranch cycle-edges) as the sum of the intersection number of its
principal subtrees.

###### Lemma 18

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$ with $v\in
V$ as its center. Let $T$ be a spanning tree of $G$ without interbranch cycle-
edges (ie: $\Delta_{T}=\varnothing$), then the following holds

$\cap_{G}(T)=\sum_{w\in N(v)}\cap_{G_{w}}(T_{w}),$

where $T_{w}$ is the principal subtree of $w\in N(v)$ considering $T$ as a
rooted tree with $v$ as its root. And $G_{w}$ is the subgraph spanned by
$T_{w}$.

Proof. As $\Delta_{T}=\varnothing$ there are no cycle-edges connecting any two
such principal subtrees. This implies that the nonempty intersections between
tree-cycles of $T$ must occur inside each subtree. This determines a partition
of $C_{T}$ and the claimed expression follows.$\square$

The following corollary in line with lemma 16 further simplifies a
hypothetical counterexample of conjecture 14.

###### Corollary 19

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$ with $v\in
V$ as its center. Let $T$ be a spanning tree of $G$ without interbranch cycle-
edges (ie: $\Delta_{T}=\varnothing$) such that $\cap(T)<\cap(T_{s})$ then

$\cap(T_{w})<\cap(G_{w}\wedge T_{s})$

for some $G_{w}$. Where $T_{w}$ is the principal subtree of $w\in N(v)$
considering $T$ as a rooted tree with $v$ as its root; $G_{w}$ is the subgraph
of $G$ spanned by $T_{w}$; $G_{w}\wedge T_{s}$ is the subtree of $T_{s}$
restricted to $G_{w}$, namely the intersection between $G_{w}$ and $T_{s}$.

Proof. First note that the $G_{w}$’s are edge disjoint since
$\Delta_{T}=\varnothing$. This partition of the edges of $G$ also determines a
partition of $T_{s}$ such that $\cap(T_{s})=\sum_{w\in N(v)}\cap(G_{w}\wedge
T_{s})$. As the parts are in a natural bijective relation since they are the
subtrees of $T$ and $T_{s}$ restricted to each $G_{w}$, we can express the
intersection number of $T$ and $T_{s}$ as follows

$\cap(T)=\sum_{w\in N(v)}\cap(T_{w})<\sum_{w\in N(v)}\cap(G_{w}\wedge
T_{s})=\cap(T_{s})$

And from the bijection we can deduce that $\cap(T_{w})<\cap(G_{w}\wedge
T_{s})$ for some $G_{w}$. $\square$

##  5 Programmatic exploration

###  5.1 Overview

In this section we present some experimental results to reinforce conjecture
14. We proceed by trying to find a counterexample based on our preceding
observations. In the first part we focus on the complete analysis of small
graphs, ie: graphs of at most 9 nodes. In the second part we analyze larger
families of graphs by random sampling instances.

###  5.2 General remarks

In the previous section we showed that the space of candidate counterexamples
of conjecture 14 can be reduced. The general picture is as follows:

  * •

Let $G=(V,E)$ be a graph that admits a star spanning tree $T_{s}$ with $v\in
V$ as its center

  * •

In the case that we can find some non-star spanning tree $T$ of $G$ such that
$\cap(T)<\cap(T_{s})$

  * •

Then we can “simplify” the instance by removing the interbranch cycle-edges
with respect to $T$ in $G$ without affecting the inequality (see lemma 16)

  * •

We can further reduce the instance by focusing on the case where $d_{T}(v)=1$,
that is: the degree of $v$ restricted to $T$ is 1 (see corollary 19)

This considerations can be used to implement algorithms to explore the space
of spanning trees more efficiently. Since the algorithms will generate
instances in this ‘reduced’ form instead of a brute force approach.

###  5.3 Complete analysis of small graphs

In this subsection we present an algorithm to explore the spanning tree space.
The algorithm proceed by exhaustively analyzing all the reduced graphs of a
given number of nodes. The size of the space increases exponentially with
respect to the number of nodes, so it has a major limitation: it can be used
to analyze only small graphs. The main part is sketched in Algorithm 1.

The details of the algorithm are the following:

  * •

The input parameter $n$ is the number of nodes of the graphs to explore

  * •

$GenerateAllTrees(n-1)$ is a function that returns the list of all trees of
$n-1$ nodes

  * •

$GenerateGraph(w,T^{\prime})$ is a function that builds a graph $G$. Based on
the tree $T^{\prime}$, it adds a new node ($v$) that will play the role of the
central node of a star spanning tree, then adds the edge $(v,w)$ to define our
candidate tree counterexample $T$. Finally adds all the other edges that link
$v$ to the rest of the nodes to obtain $G$. It returns the graph $G$ and
($\bar{\Delta}$) the set of “possible” non-interbranch cycle edges.

  * •

$IntersectionNumber(\phi,G)$ is a function that calculates the intersection
number of $T$ in $G\cup\phi$, where $\phi\subset\bar{\Delta}$ is a subset of
supplementary edges of $G$.

  * •

$StarIntersectionFormula(\phi,G)$ is a function that calculates the
intersection number of the star spanning tree in $G\cup\phi$

  * •

The algorithm finds a counterexample of the conjecture if:
$IntersectionNumber(\phi,G)<StarIntersectionFormula(\phi,G)$

Note that the analyzed graphs are reduced in the sense explained previously.
The cycle-edges are non-interbranch by construction and $d_{T}(v)=1$ since $v$
is only connected to $w$ in $T$ (ie. there is a single principal subtree). As
the algorithm iterates over all possible spanning subtrees $T^{\prime}$ and
all the combinations of possible non-interbranch cycle-edges, every instance
is guaranteed to be explored at least once.

Algorithm 1 CounterexampleSearch($n$)

$\mathscr{T}\leftarrow GenerateAllTrees(n-1)$

for each tree $T^{\prime}\in\mathscr{T}$ do

for each node $w\in T^{\prime}$ do

$G,\bar{\Delta}\leftarrow GenerateGraph(w,T^{\prime})$

for each subset $\phi\subset\bar{\Delta}$ do

check $(IntersectionNumber(\phi,G)<$

$StarIntersectionFormula(\phi,G))$

Table I: Small instances results nodes | instances (approx.)
---|---
4 | 5
5 | 33
6 | 251
7 | 4200
8 | 125000
9 | 7900000

To generate all non-isomorphic trees of $|V|-1$ nodes we used the package
_nauty_ [McKay and Piperno, 2014].

The proposed algorithm did not find a counterexample of the intersection
conjecture. Table LABEL:tab:small-inst shows the size of the experiments. The
column _nodes_ is the number of nodes of the graph family, ie: $|V|$. The
column _instances_ is the number of instances processed.

###  5.4 Random sampling of large graphs

In this section we present another algorithm to explore the spanning tree
space. The strategy in this case is to sample reduced graphs of a given number
of nodes. The main part is sketched in Algorithm 2.

The details of the algorithm are the following:

  * •

The input parameters are: $n$ the number of nodes of the graphs and $k$ the
size of the sample

  * •

$GenerateRandomTree(n)$ is a function that returns a random tree $T$ of $n$
nodes, where the node $v$ that will play the role of center of the star has
degree 1 restricted to $T$.

  * •

$GenerateGraph(T)$ is a function that builds a reduced graph $G$. Based on the
tree $T$, adds all the edges that link $v$ to the rest of the nodes to obtain
$G$. It returns the graph $G$ and ($\bar{\Delta}$) a random set of non-
interbranch cycle edges.

  * •

$IntersectionNumber(\phi,G)$ same as algorithm 1

  * •

$StarIntersectionFormula(\phi,G)$ same as algorithm 1

  * •

The algorithm finds a counterexample of the conjecture if:
$IntersectionNumber(\phi,G)<StarIntersectionFormula(\phi,G)$

Algorithm 2 CounterexampleRandomSearch($n,k$)

for i := 1..k do

$T\leftarrow GenerateRandomTree(n)$

$G,\bar{\Delta}\leftarrow GenerateRandomGraph(T)$

check $(IntersectionNumber(\phi,G)<$

$StarIntersectionFormula(\phi,G))$

Table II: Random instances results nodes | instances
---|---
25 | 3000000
50 | 300000
100 | 30000
200 | 15000
400 | 300

We used a uniformly distributed random number generator. To generate trees we
used a simple algorithm that randomly connects a new node to an already
connected tree. The non-interbranch cycle-edge set is built by associating a
_Bernoulli_ trial to each such possible edge. To achieve some diversity for
each tree we built three different sets to obtain a sparse, medium and dense
sets based on corresponding probabilities $0.1$, $0.5$, $0.9$.

The proposed algorithm did not find a counterexample of the intersection
conjecture. Table LABEL:tab:random-inst shows the size of the experiments. The
column _nodes_ is the number of nodes of the graph family, ie: $|V|$. The
column _instances_ is the number of instances processed.

##  6 Conclusion

In this article we introduced the _Minimum Spanning Tree Cycle Intersection_
(MSTCI) problem.

We proved by enumerative arguments that the star spanning trees are the unique
solutions of the problem in the context of complete graphs.

We conjectured a generalization to the case of graphs (not necessarily
complete) that admit a star spanning tree. In this sense we showed that the
star spanning tree is a local minimum in the domain of the _spanning tree
graph_. We deduced a closed formula for the tree intersection number of star
spanning trees in this setting. We proposed two ideas to attempt to find a
counterexample of the conjecture. Those ideas were the basis of two strategies
to programatically explore the space of solutions in the pursue of a
counterexample. The negative result of the experiments suggest that the
conjecture is well posed. Unlike the complete graph context, in this slightly
more general case, star spanning trees are not unique; there are other
spanning trees $T$ such that $\cap(T_{s})=\cap(T)$.

We proved a general result that shows that spanning trees that solve the MSTCI
problem don’t depend on some intrinsic property but on their particular
embedding in the ambient graph.

An interesting direction of research is to consider the MSTCI problem for
other families of graphs, ie.: graphs that do not admit a star spanning tree.
Of particular interest is the class of triangular meshes, ie.: graphs that
model the immersion of compact surfaces in the 3D euclidean space.

Another interesing direction of research is related to proving to which
complexity class the MSTCI problem belongs to. In case of belonging to the NP-
hard class, it will be important to find approximate, probabilistic and
heuristic algorithms.

## References

  * [Botsch, 2010] Botsch, M. and Kobbelt, L. and Pauly, M. and Alliez, P. and Lévy, B.,  Polygon Mesh Processing,  A. K. Peters, 2010.
  * [Cartan, 1956] Cartan, H. P. and Eilenberg, S.,  Homological Algebra,  Princeton University Press, 1956.
  * [Estrada, 1998] Estrada E. and Torres L. and Rodríguez L. and Gutman I.,  An atom-bond connectivity index: modelling the enthalpy of formation of alkanes,  Indian J. Chem. 37A (1998) 849–855.
  * [Furtula, 2009] Furtula B. and Graovac A. and Vukičević D.,  Atom-bond connectivity index of trees,  Discrete Appl. Math. 157 (2009) 2828–2835.
  * [Gutman, 2013] Gutman I.,  Degree-based topological indices,  Croat. Chem. Acta 86 (2013) 351–361.
  * [Dewan, 2010] Dewan I.,  Graph Homology and Cohomology.
  * [McKay and Piperno, 2014] McKay B.D. and Piperno A.,  Practical Graph Isomorphism, II,  Journal of Symbolic Computation, 60 (2014), pp. 94-112.
  * [McKee and McMorris, 1999] McKee T.A and McMorris F.R.,  Topics in intersection graph theory,  SIAM monographs on discrete mathematics and applications, 1999\.
  * [Tutte, 1965] Tutte W.T.,  Lecture on Matroids,  Mathematics and Mathematical Physics, Vol. 69B Nos. 1 and 2 (1965).