# Loose edge-connection of graphs

1Christoph Brause, 2Stanislav Jendrol’, 1Ingo Schiermeyer

1TU Bergakademie Freiberg
Institute of Discrete Mathematics and Algebra
09596 Freiberg, Germany
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>

2P.J. Šafárik University
Jesenná 5, 04001 Košice, Slovakia
E-mail<EMAIL_ADDRESS>

###### Abstract

In the last years, connection concepts such as rainbow connection and proper
connection appeared in graph theory and obtained a lot of attention. In this
paper, we investigate the loose edge-connection of graphs. A connected edge-
coloured graph $G$ is loose edge-connected if between any two of its vertices
there is a path of length one, or a bi-coloured path of length two, or a path
of length at least three with at least three colours used on its edges. The
minimum number of colours, used in a loose edge-colouring of $G$, is called
the loose edge-connection number and denoted $\operatorname{lec}(G)$. We
determine the precise value of this parameter for any simple graph $G$ of
diameter at least 3. We show that deciding, whether $\operatorname{lec}(G)=2$
for graphs $G$ of diameter 2, is an NP-complete problem. Furthermore, we
characterize all complete bipartite graphs $K_{r,s}$ with
$\operatorname{lec}(K_{r,s})=2$.

Keywords: edge colouring, loose edge-connection, $2$-connected graphs, trees

##  1 Introduction and motivation

In this paper, we consider simple and undirected graphs only. For notation and
graph theoretic terminology, we generally follow the book of West [18]. Aside
from that, we denote by $n=|V(G)|$ the order of a graph $G$ and by $m=|E(G)|$
the size of $G$. The degree of a vertex $v$ of $G$, denoted by $\deg_{G}(v)$,
is the number of edges of $G$ incident with the vertex $v$. We will denote by
$\Delta(G)$ and by $\delta(G)$ the maximum degree and the minimum degree of
the graph $G$. Furthermore, for simplicity, we denote by $[k,l]$ the set of
integers $\\{k,k+1,\ldots,l\\}$ if $k\leq l$. Note that $[k,l]=\emptyset$ for
$k>l$.

Two edges are adjacent if they share a common vertex. Two edges are semi-
adjacent if they are not adjacent but there is a third edge that is adjacent
to both of them.

The weight $w(e)$ of an edge $e=uv$ is the sum of degrees of its end-vertices,
i.e. $w(e)=deg(u)+deg(v)$. The reduced maximum weight $\mathrm{rw}(G)$ of the
graph $G$ is defined as $\mathrm{rw}(G)=max\\{w(e)-1:e\in E(G)\\}$.

Let $G$ be a graph. A _path_ $L$ in $G$ is a subgraph of $G$ consisting of a
vertex set $\\{v_{1},v_{2},\ldots,v_{k}\\}$ and edge set
$\\{v_{1}v_{2},v_{2}v_{3},\ldots,v_{k-1}v_{k}\\}$. For simplicity, we write
$L:v_{1}v_{2}\ldots v_{k}$ and, if $L$ contains two vertices $u,v$, then we
denote by $uLv$ the subpath of $L$ between $u$ and $v$. Two vertices, say
$u,v\in V(G)$, are _connected_ by a path $L$ if the end vertices of $L$ are
$u$ and $v$. Such a path is denoted as an $u,v$-path.

The circumference of a graph $G$, $\mathrm{cir}(G)$, is the length of the
longest cycle. We will denote by $C_{k}$ (resp. $K_{k}$, resp. $K_{r,s}$) the
cycle (resp. the complete graph, resp. complete bipartite graph) on $k\geq 3$
(resp. $k$, resp. $r\geq 1$ and $s\geq 1$) vertices.

Let $\mathbb{A}=\\{a,b,c,\ldots\\}$ be a finite alphabet, i.e. a set of
colours, digits, symbols, …, whose elements are called _letters_. A _word_ $A$
of length $k$ over $\mathbb{A}$ is a sequence of letters, say
$A:a_{1}a_{2}a_{3}\ldots a_{k}$ where $a_{i}\in\mathbb{A}$ for all
$i\in[1,k]$. Let us recall some properties that words can have (see e.g.
[10]). A word $A$ is

… proper

if consecutive letters are not identical,

… rainbow

if it does not contain two identical letters,

… conflict-free

if at least one letter occurs exactly once in $A$,

… monochromatic

if all letters are identical,

… odd

if each letter of the alphabet $\mathbb{A}$ appears an odd number of times or
zero times in $A$,

… loose

if either $A$ consists of exactly one letter, of exactly two different
letters, or has at least three different letters,

Using properties of words over an alphabet $\mathbb{A}$, Brause, Jendrol’, and
Schiermeyer [3] have introduced a graph theoretic meta-concept as follows.

Consider a graph $G$. If there is an edge colouring $\phi:E(G)\to\mathbb{A}$,
then we can associate to a path $L=v_{1}v_{2}\ldots v_{k}$ with $v_{i}\in
V(G)$ for all $i\in[1,k]$, $L$ being a subgraph of $G$, a word
$\phi(v_{1}v_{2})\phi(v_{2}v_{3})\ldots\phi(v_{k-1}v_{k})$.

Now, let $\mathcal{P}$ be a property of words over the alphabet $\mathbb{A}$.
Considering an edge colouring $\phi:E(G)\to\mathbb{A}$ we say that _$L$ has
the property $\mathcal{P}$_ if the associated word
$\phi(v_{1}v_{2})\phi(v_{2}v_{3})\ldots\phi(v_{k-1}v_{k})$ has property
$\mathcal{P}$.

Let $G$ be a connected graph, $\mathbb{A}$ be an alphabet with $k$ letters,
$\mathcal{P}$ be a property of words, and $\phi:E(G)\rightarrow\mathbb{A}$ be
an edge-colouring. The edge-colouring _$\phi$_ makes $G$ to be $\mathcal{P}$
edge-connected if any two distinct vertices of $G$ are connected by a path
having the property $\mathcal{P}$. The minimum integer $k$, for which there
exists an edge colouring $\phi:E(G)\to\mathbb{A}$ with $|\mathbb{A}|=k$ that
makes $G$ to be $\mathcal{P}$ edge-connected, is the $\mathcal{P}$ edge-
connection number of $G$.

From a practical point of view, the $\mathcal{P}$ edge-connection of graphs
plays an important role for security and accessibility in communication
networks. While the information which one sends through a network from one
node to another has to be protected by passwords, it is of high importance
that the password sequences of information transferring paths meet some
prescribed requirements. Since managing a whole bunch of passwords, that are
assigned to direct information transferring paths between two nodes, is
expensive, it is a natural question to ask for a minimum number of passwords
securing the information transferring paths. By representing each node as a
vertex, each direct information transferring path between two nodes as an
edge, each possible password by a different colour, and the prescribed
requirements for the password sequences of information transferring paths by a
property $\mathcal{P}$ for a word over the alphabet of colours, the above
problem is translated to finding the $\mathcal{P}$ edge-connection number of a
path.

Chartrand et al. [8] introduced the concept of rainbow connection; that is,
the concept of the $\mathcal{P}$ edge-connection where property $\mathcal{P}$
is rainbow. Let $\mathrm{rc}(G)$ denote the rainbow edge-connection number.
Returning to the mathematical problem and its applications, the $\mathcal{P}$
edge-connection number of graphs have been intensively studied for some of the
mentioned properties, for example if property $\mathcal{P}$ is rainbow [7, 8,
12, 13, 14, 15], proper [1, 2], odd [3], or conflict-free [11]. In this paper,
we concentrate on the loose edge-connection, which is a relaxation of the
concepts rainbow connection and conflict-free connection. A motivation to
study the loose edge-connection comes also from the loose-colouring of
embedded graphs, see e.g. [17], [9], or [10]. Note, that the loose vertex-
connection of simple connected graphs is studied in a more general version in
[4].

We say that a path $L$, which is a subgraph of a graph $G$ with an edge
colouring $\phi:E(G)\to[1,k]$, is _loose edge-coloured_ if the path consists
of one edge, or exactly two differently coloured edges, or has at least three
edges that are coloured with at least three distinct colours.

A connected graph $G$, coloured by an edge colouring
$\phi:E(G)\rightarrow[1,k]$, is said to be _loose edge-connected_ if any two
distinct vertices are connected by a loose coloured path. The least integer
$k$, for which we have an edge colouring $\phi:E(G)\to[1,k]$ that makes $G$
loose edge-connected, is called the _loose edge-connection number_ of $G$,
denoted by $\operatorname{lec}(G)$.

Observe, that any rainbow connected graph is also loose connected. Also, if a
graph $G$ is a spanning subgraph of a graph $H$ and $\operatorname{lec}(G)=k$,
then $\operatorname{lec}(H)\leq k$.

In the sequel, a path in an edge coloured graph will be called _monochromatic_
, _bi-chromatic_ , and _loose_ if its edges are coloured with exactly one
colour, exactly two colours, and with at least three colours, respectively.

A _block_ $B$ of a connected graph $G$ is an induced subgraph of $G$ of order
at least $2$ which is $2$-connected and, with respect to this condition,
maximal; that is, $B$ is $2$-connected, but for every $v\in V(G)\setminus
V(B)$, the graph $G[V(B)\cup\\{v\\}]$ is disconnected or contains a cut-
vertex. We note that if $n(B)\geq 3$, then we say that $B$ is _non-trivial_.
Otherwise, if $n(B)=2$ and $B$ is isomorphic to $K_{2}$, we say that $B$ is
_trivial_.

The block-cutpoint graph of a graph $G$ is a bipartite graph $B(G)$ in which
one partite set consists of the cut-vertices of $G$, and the other has a
vertex $b_{i}$ for each block $B_{i}$ of $G$. We include $vb_{i}$ as an edge
of $B(G)$ if and only if $v\in B_{i}$. When $G$ is connected, its block-
cutpoint graph is a tree whose leaves are blocks of $G$. These blocks are
called _leaf blocks_. If $B$ is a trivial block and $e\in E(B)$ is the edge of
$B$, then $e$ is a _cut-edge_ of $G$; that is, $G-e$ is disconnected.

Let $C(G)$ be the graph induced on the set $E(C)\subseteq E(G)$ of all cut-
edges of $G$ consisting of all vertices of $G$ that are incident to the edges
of the set $E(C)$. More precisely,

$V(C(G))=\left\\{\bigcup_{uv\in E(C)}\\{u,v\\}\right\\}\quad{\rm and}\quad
E(C(G))=E(C).$

We denote by $\Delta(C(G))$ the maximum degree of $C(G)$. The graph $C(G)$ is
called the _cut-edge graph_ of $G$. (see [18], p. 156).

Let $F_{t}$ be a graph obtained from a graph $F$ by attaching $t$ leaves,
$t\geq 0$, to every vertex of $F$.

Let $H$ be a non-trivial connected graph, $F$ be a $2$-connected graph, and
$t\geq 0$ be an integer. A graph $H$ is of type (t, F) if $F\subseteq
H\subseteq F_{t}$, and $H$ contains a vertex adjacent with exactly $t$ leaves.

The rest of this paper is organized as follows: Sections 2 - 7 contain some
preliminary statements that are necessary for the proofs of our main results.
In Sections 8 the characterization of all complete bipartite graphs with
$\operatorname{lec}(K_{r,s})=2$ is given. In Section 10, the precise values of
the loose edge-connection number for all non-trivial connected graphs of
diameter at least 3 are determined .

##  2 Loose edge-connection of trees

######  Lemma 1.

If $G$ is a tree of the reduced weight $\mathrm{rw}(G)$, then
$\operatorname{lec}(G)=\mathrm{rw}(G)$.

###### Proof.

For the edge-colouring of $G$ we use the following adaptation of the FSB
algorithm (see e. g. [18], p. 99).

For a tree $G$ let $M=[1,\mathrm{rw}(G)]$ be the set of colours.

Input: A tree $G$, a start vertex $u$, and the colour set $M$.

Idea: Maintain a set $R$ of vertices that have been reached by coloured edges
but not searched and a set $S$ of vertices that have been searched, i.e.
vertices of the set $S$ are incident only with coloured edges. The set $R$ is
maintained as a First-In First-Out list (queue), so the first vertices are the
first vertices explored.

Initialization: $R=\\{u\\},S=\emptyset$.

Iteration: As long as $R\neq\emptyset$, we search for the first vertex $v$ of
$R$. Then we colour each edge $e=vw$ of $G$ incident with $v$ and $w\notin
R\cup S$, with colour $\varphi(e)=\min\\{M\setminus F(e)\\}$. (Here set $F(e)$
is the set of colours used till now on edges adjacent or semi-adjacent with
$e$.) Next the neighbour $w$ of $v$ is added to the back of $R$. If all the
edges incident with $v$ are coloured, the vertex $v$ is removed from the front
of $R$ and is placed in $S$.

It is easy to see that this algorithm works properly. ∎

##  3 Graphs of type $R$

A graph $H$ is of type $(t,R)$ if $R=C_{3}=K_{3}$. Then $R_{t}$ is the graph
obtained from $K_{3}$ by attaching $t$ leaves on every vertex of it. Let
$V(R_{t})=\\{x,y,z,x_{i},y_{i},z_{i};i\in[1,t]\\}$,
$E(R_{t})=\\{xy,xz,zy,zz_{i},yy_{i},xx_{i};i\in[1,t]\\}$. Observe that
$\Delta(C(R_{t}))=\mathrm{rw}(C(R_{t}))=t$.

######  Lemma 2.

If $H$ is a graph of type $(t,R)$, then the following hold:

  1. 1.

If $t=1$ and $|E(C(H))|=1$, then $\operatorname{lec}(H)=2$ .

  2. 2.

If $t\leq 2$ and $|E(C(H))|\geq 2$, then $\operatorname{lec}(H)=3$.

  3. 3.

If $t\geq 3$, then $t\leq\operatorname{lec}(H)\leq t+1$.

Moreover, $\operatorname{lec}(H)=t+1$ if and only if $H$ contains two vertices
$b_{1}$ and $b_{2}$ such that $\deg_{C(H)}(b_{1})+deg_{C(H)}(b_{2})\geq 2t-1$.

###### Proof.

Case 1. First we consider the graph $R_{t}$. Observe that
$\operatorname{diam}(R_{t})=3$ and
$\operatorname{lec}(R_{t})\geq\max\\{3,t\\}$. The following loose edge-
colouring with three colours is suitable for $R_{1}$:
$\varphi(xy)=\varphi(zz_{1})=1$, $\varphi(yz)=\varphi(xx_{1})=2$, and
$\varphi(xz)=\varphi(yy_{1})=3$.

The colouring $\varphi(xx_{i})=\varphi(yy_{i})=\varphi(zz_{i})=i+1$ for every
$i\in[3,t]$, $\varphi(xy)=\varphi(xx_{1})=\varphi(yy_{1})=1$,
$\varphi(xz)=\varphi(xx_{2})=\varphi(zz_{1})=2$, and
$\varphi(yz)=\varphi(yy_{2})=\varphi(zz_{2})=3$ is a suitable loose edge-
colouring of $R_{t}$ with $t+1$ colours for all $t\geq 2$.

We need to show that $t+1$ colours are necessary for $t\geq 3$. We start with
the graph $R_{3}$. Assume that three colours are enough to get a loose
connection of $R_{3}$. Then all three leaves attached to each vertex of
$C_{3}$ of $R_{3}$ are coloured with three different colours. Consider the
vertices $x$ and $y$. Let, w.l.o.g.,
$\varphi(xx_{i})=\varphi(yy_{i})=\varphi(zz_{i})=i,i\in[1,3]$. There is a
loose $x_{i},y_{i}$-path in $R_{3}$ such that
$\\{\varphi(xz),\varphi(yz)\\}=[1,3]\setminus\\{i\\}$. But for any $j,j\neq
i$, we also have $\\{\varphi(xz),\varphi(yz)\\}=[1,3]\setminus\\{j\\}$. A
contradiction.

Assume that there is a loose colouring of $R_{t}$ with $t$ colours for $t\geq
4$, $\varphi(xx_{i})=\varphi(yy_{i})=\varphi(zz_{i})=i,i\in[1,t]$, and let
colours $1,2$, and $3$ are used on the edges of $C_{3}$. If we delete from
$R_{t}$ the edges coloured with colour $k\in[4,t]$, we get a loose colouring
of $R_{3}$ with three colours. This contradicts the nonexistence of such a
colouring of $R_{3}$.

Case 2. Let $t\geq 3$. Consider first the graph
$G_{1}=R_{t}\setminus\\{xx_{t},xx_{t-1},yy_{t},yy_{t-1}\\}$. It has the
following loose edge-colouring $\varphi$ with $t$ colours:
$\varphi(xx_{i})=\varphi(yy_{i})=\varphi(zz_{i})=i$, $i\in[1,t-3]$,
$\varphi(xx_{t-2})=\varphi(xz)=\varphi(zz_{t})=t$,
$\varphi(yy_{t-2})=\varphi(yz)=\varphi(zz_{t-1})=t-1$, and
$\varphi(xy)=\varphi(zz_{t-2})=t-2$. It is easy to see that any graph $H$ of
type $(t,R)$ which is a subgraph of $G_{1}$ has a loose edge-colouring with
$t$ colours.

We need to show that $t+1$ colours are necessary for $t\geq 3$ if $H$ has two
vertices, say, $x$ and $z$, whose degree sum in $C(H)$ is at least $2t-1$.
Assume for the contrary that the graph $H$ has a loose edge-colouring
$\varphi$ with $t$ colours. Consider the graph $H$ and its vertices
$x,x_{i},i\in[1,t-1]$, $z$, and $z_{j},j\in[1,t]$. Let, w.l.o.g.,
$\varphi(xx_{i})=\varphi(zz_{i})=i,i\in[1,t-1]$, and $\varphi(zz_{t})=t$. Let
$\varphi(xz)=c$. Then the edges $xy$ and $yz$ have to be coloured with
different colours, say $a$ and $b$. Then there is neither a loose
$x_{a},z_{a}$-path nor a loose $x_{b},z_{b}$-path in $H$. A contradiction.

Case 3. Let $t\leq 2$. If $H$ contains at least three leaves, then
$\operatorname{diam}(H)=3$, $H\subseteq R_{2}$, and, by Case 1,
$\operatorname{lec}(H)=3$. If $H$ has exactly two leaves, then one can easily
show that $\operatorname{lec}(H)=3$ and an edge-colouring of $C_{3}$ consists
of three different colours. If $H$ has one leaf, we colour all the edges of
the $3$-cycle of $C_{3}$ with colour $1$ and remaining edges of $H$with colour
$2$.

This completes the proof of our Lemma 2. ∎

##  4 Graphs of type $Q$

Let $Q_{t}$ be a graph obtained from the cycle $C_{4}$ by attaching $t$
leaves, $t\geq 1$, to every vertex of $C_{4}$. Let
$V(Q_{t})=\\{x,y,v,w,x_{i},y_{i},v_{i},w_{i};i\in[1,t]\\}$ and
$E(Q_{t})=\\{vx,wx,vy,wy,xx_{i},yy_{i},vv_{i},ww_{i};i\in[1,t]\\}$.

######  Lemma 3.

If $H$ is a graph of type $(t,Q)$ with $C_{4}\subseteq Q\subseteq K_{4}$, then
the following hold:

  1. (i)

If $1\leq t\leq 2$, then $3\leq\operatorname{lec}(H)\leq 4$. Moreover,
$\operatorname{lec}(H)=4$ if and only if the cycle $C_{4}$ of $H$ contains no
diagonal and at least three vertices each adjacent to exactly two leaves.

  2. (ii)

If $t=3$, then $3\leq\operatorname{lec}(H)\leq 4$. Moreover,
$\operatorname{lec}(H)=4$ if and only if the cycle $C_{4}$ of $H$ does not
contain any diagonal, or $C_{4}$ contains a diagonal $xy$, $\deg_{C(H)}(x)=3$
and $\deg_{C(H)}(y)=3$, or $\deg_{C(H)}(y)=2$ and
$\deg_{C(H)}(v)=\deg_{C(H)}(w)=3$.

  3. (iii)

If $t\geq 4$, then $\operatorname{lec}(H)=t$ .

###### Proof.

Case 1. First we consider the graph $Q_{t}$. Observe that
$\operatorname{diam}(Q_{t})=4$ and
$\operatorname{lec}(Q_{t})\geq\max\\{3,t\\}$. A suitable loose edge-colouring
of $Q_{1}$ with three colours is: $\varphi(vx)=\varphi(wy)=a,\varphi(vy)=c$,
$\varphi(wx)=b$ and
$\varphi(xx_{1})=\varphi(yy_{1})=c,\varphi(vv_{1})=\varphi(ww_{1})=b$.

A suitable loose edge-colouring of $Q_{t},t\geq 2$, with at least four colours
follows: $\varphi(vx)=a,\varphi(wx)=b,\varphi(wy)=c,\varphi(vy)=d$, and
$\varphi(xx_{i})=\varphi(yy_{i})=\varphi(vv_{i})=\varphi(ww_{i})=i,i\in[1,t]$.
Here $\\{a,b,c,d\\}\subseteq[1,t]$. This gives $\operatorname{lec}(Q_{2})\leq
4$, $\operatorname{lec}(Q_{3})\leq 4$, and $\operatorname{lec}(Q_{t})=t$ for
$t\geq 4$.

Case 2. If $t\geq 4$, then the loose colouring of $H$ with $\max\\{3,t\\}$
colours follows from the loose colouring of $Q_{t}$ with $t$ colours.

Case 3. Let $t=2$.

Subcase 3.1 Let on $C_{4}$ of $H$ there are at most two vertices each adjacent
with exactly two leaves. Then it is a subgraph of one of the following graphs:
$H_{1}=(V_{1},E_{1})$ with
$V_{1}=\\{x,x_{1},x_{2},v,v_{1},v_{2},y,y_{1},w,w_{1}\\}$,
$E_{1}=\\{xv,xx_{1},xx_{2},vv_{1},vv_{2},vy,yy_{1},yw,ww_{1},wx\\}$ and a
loose edge-colouring $\phi(xx_{1})=\phi(vv_{1})=\phi(vy)=\phi(yy_{1})=a$,
$\phi(xv)=\phi(yw)=b$, $\phi(xx_{2})=\phi(wx)=\phi(vv_{2})=\phi(ww_{1})=c$.
$H_{2}=(V_{2},E_{2})$ with
$V_{2}=\\{x,x_{1},x_{2},v,v_{1},y,y_{1},y_{2},w,w_{1}\\}$,
$E_{2}=\\{xv,xx_{1},xx_{2},vv_{1},vy,yy_{1},yy_{2},yw,ww_{1},wx\\}$ and a
loose edge-colouring $\phi(xx_{1})=\phi(vv_{1})=\phi(vy)=\phi(yy_{1})=a$,
$\phi(xv)=\phi(yw)=c$, $\phi(xx_{2})=\phi(wx)=\phi(yy_{2})=\phi(ww_{1})=b$.

It is easy to see that the graph $H$ has a loose edge-colouring with three
colours obtained from one of the above colouring of the graph $H_{1}$ or
$H_{2}$.

Subcase 3.2 Let on $C_{4}$ of $H$ there are at least three vertices, say
$x,v$, and $y$, each adjacent with exactly two leaves. Assume that there is a
loose edge-colouring $\phi$ with three colours. We can assume, w.l.o.g., that
$\phi(xx_{1})=\phi(vv_{1})=a$ and $\phi(xx_{2})=b$.

Subcase 3.2.1 Let $\phi(xv)=a$. Then $\\{\phi(xw),\phi(wy)\\}=\\{b,c\\}$,
otherwise there is no loose $x_{1},y$-path, and
$\\{\phi(vy),\phi(wy)\\}=\\{b,c\\}$, otherwise there is no loose
$v_{1},w$-path in $H$. This gives, in order, $\phi(vv_{2})=c$ (because a loose
$x_{2},v_{2}$-path), $\phi(xw)=b$, $\phi(wy)=c$, $\phi(vy)=c$ (because a loose
$x_{2},y$-path) and $\phi(wy)=b$ (because a loose $v_{1},w$-path), a
contradiction.

Subcase 3.2.2 Let $\phi(xv)=b$. Then $\\{\phi(xw),\phi(wy)\\}=\\{a,c\\}$ and
$\phi(vy)=c$ because of a loose $x_{2},y$-path and loose $x_{1},y$-path. This
implies that there is no $x_{1},v_{1}$-path, a contradiction.

Subcase 3.2.3 Let $\phi(xv)=c$. Then $\\{\phi(xw),\phi(vy)\\}=\\{a,b\\}$,
$\phi(wy)=c$ $\phi(vv_{2})=b$, and, w.l.o.g., $\phi(yy_{1})=a$,
$\phi(yy_{2})=b$. This implies the nonexistence a loose $v_{i},y_{i}$-path in
$H$ for some $i\in\\{1,2\\}$, a contradiction.

Subcase 3.3 Let the cycle $C_{4}$ of $H$ contains a diagonal $xy$, that is $H$
contains a block which is the diamond. Then $H$ is a subgraph of the graph
$D_{2}\cup\\{xy\\}$. This graph has the following loose edge-colouring $\phi$.
$\phi(xx_{1})=\phi(vv_{1})=\phi(yy_{1})=\phi(vy)=a$,
$\phi(xw)=\phi(xx_{2})=\phi(yy_{2})=\phi(ww_{1})=b$, and
$\phi(xv)=\phi(xy)=\phi(vv_{2})=\phi(wy)=\phi(ww_{2})=c$. From this colouring
we can easily get a required colouring of $H$.

Case 4. Let $t=3$ and $H$ does not contain a diagonal $xy$. Assume, that $H$
has a loose edge-colouring with tree colours and $\deg_{C(H)}(x)=3$. Let the
neighbour leaf $x_{i}$ of $x$ be adjacent to $x$ via edge $xx_{i}$ coloured
with a colour $i$. Then between $x$ and $y$ there should be three mutually
different bi-chromatic $x,y$-paths but there exactly two ones. A
contradiction, which shows that at least four colour are necessary for a loose
edge-colouring of $H$. Such a colouring is induced by the colouring of $Q_{3}$
of the Case 1 because $H\subseteq Q_{3}$.

Case 5. Let $t=3$ and $H$ contain a diagonal $xy$. Denote by $D$ the diamond,
that is the subgraph of $H$ induced on the vertex set $\\{x,v,y,w\\}$. Assume,
that $H$ has a loose edge-colouring $\varphi$ with tree colours.

Subcase 5.1. Let $\deg_{C(H)}(x)=3$. Let the neighbour leaf $x_{i}$ of $x$ be
adjacent to $x$ via edge $xx_{i}$ coloured with a colour $i$.

Subcase 5.1.1. Let $\deg_{C(H)}(y)=3$ and let the neighbour leaf $y_{i}$ of
$y$ is adjacent to $y$ via the edge $yy_{i}$ coloured with colour
$i,i\in\\{1,2,3\\}$. As $H$ has a loose edge-colouring with three colours,
there should be three distinct bi-chromatic $x,y$-paths of length two. But
there are exactly two, a contradiction.

Subcase 5.1.2. Let $\deg_{C(H)}(y)=2$ Let
$\bar{Q}_{3}=(Q_{3}\setminus\\{yy_{1},ww_{3}\\})\cup\\{xy\\}$. The graph
$\bar{Q}_{3}$ has the following loose edge-colouring:
$\varphi(vx)=\varphi(wx)=1$,
$\varphi(xx_{1})=\varphi(vv_{1})=\varphi(ww_{1})=1$;
$\varphi(yw)=\varphi(yy_{2})=2$,
$\varphi(xx_{2})=\varphi(vv_{2})=\varphi(ww_{2})=2$, and
$\varphi(vy)=\varphi(xy)=\varphi(xx_{3})=3$,
$\varphi(yy_{3})=\varphi(vv_{3})=3$. Observe, that each subgraph
$H\subseteq\bar{Q}_{3}$ of type $(t,Q)$ containing the diamond $D$ has a loose
edge-colouring with three colours.

To the end of the proof in this case it is enough to show that the graph
$Q^{*}=(Q_{3}\setminus\\{yy_{3}\\})\cup\\{xy\\}$ does not have any loose edge-
colouring with three colours. Assume the opposite. Let it has such a colouring
$\varphi$.

Let the neighbour leaf $y_{i}$ of $y$ be adjacent to $y$ via the edge $yy_{i}$
coloured with a colour $i\in\\{1,2\\}$. Then the following situation,
w.l.o.g., appears in $Q^{*}$: $\\{\varphi(xv),\varphi(vy)\\}=\\{1,3\\}$ and
$\\{\varphi(xw),\varphi(wy)\\}=\\{2,3\\}$ because there are loose
$x_{1},y_{1}$-path and $x_{2},y_{2}$-path of length al least three. This,
w.l.o.g., enforces $\varphi(xy)=1$ and then no loose $x_{3},v_{3}$-path
exists. A contradiction

Subcase 5.1.3. Let $\deg_{C(H)}(y)\leq 1$ and let $y_{1}$ be the neighbour of
$y$. Then $H\subseteq G^{1}=(Q_{3}\setminus\\{y_{2},y_{3}\\})\cup\\{xy\\}$.
The graph $G^{1}$ has the following loose edge-colouring with three colours:
$\varphi(xv)=\varphi(xw)=$ $\varphi(xx_{1})=$
$\varphi(ww_{1})=\varphi(vv_{1})=1$, $\varphi(xy)=\varphi(ww_{2})=$
$\varphi(xx_{2})=$ $\varphi(yw)=\varphi(vv_{2})=2$, and
$\varphi(yv)=\varphi(ww_{3})=$ $\varphi(xx_{3})=$
$\varphi(yy_{1})=\varphi(vv_{3})=3$. It is easy to see that colouring
$\varphi$ of $G^{1}$ just described has the required properties of loose edge-
coloring. From this colouring of $G^{1}$ one easily derives a loose edge-
colouring with three colours of any subgraph $H$ of $G^{1}$, which is of of
type $(t,Q)$.

Subcase 5.2. Let $\deg_{C(H)}(x)\leq 2$ and $\deg_{C(H)}(y)\leq 2$. Consider
the graph $G^{*}=Q_{3}\setminus\\{xx_{2},yy_{1}\\}\cup\\{xy\\}$. The following
edge-colouring $\varphi$ of $G^{*}$ is a loose one:
$\varphi(xv)=\varphi(xw)=\varphi(xx_{1})=1$,
$\varphi(vv_{1})=\varphi(ww_{1})=1$,
$\varphi(vy)=\varphi(wy)=\varphi(vv_{2})=2$,
$\varphi(yy_{2})=\varphi(ww_{2})=2$,
$\varphi(xy)=\varphi(xx_{3})=\varphi(vv_{3})=3$, and
$\varphi(yy_{3})=\varphi(ww_{3})=3$. From this colouring of $G^{*}$ one easily
derives a loose edge-colouring with three colours of any subgraph $H$ of
$G^{*}$, which is of type $(t,Q)$.

Case 6. Let the graph $H$ contain both diagonals $xy$ and $vw$. Then
$H\subseteq G^{2}=Q_{3}\cup\\{xy,vw\\}$. It is easy to find a suitable loose
edge-colouring of $G^{2}$ with three colours when we color edges $xv$ and $yw$
with colour $1$, the edges $xw$ and $yv$ with colour $2$, and the edges $xy$
and $vw$ with colour $3$.

This finishes the proof of Lemma 3 ∎

##  5 Graphs of type $P$

Let $P_{t}$ be a graph obtained from the cycle $C_{5}$ by attaching $t$
leaves, $t\geq 1$, to every vertex of $C_{5}$. Let
$V(P_{t})=\\{x,y,z,u,v,x_{i},y_{i},z_{i},u_{i},v_{i};i\in[1,t]\\}$ and
$E(P_{t})=\\{ux,vx,uy,vz,yz,xx_{i},yy_{i},zz_{i},uu_{i},vv_{i};i\in[1,t]\\}$.

######  Lemma 4.

If $H$ is of type $(t,P)$ with $C_{5}\subseteq P\subseteq K_{5}$, then the
following statements hold:

  1. (i)

If $1\leq t\leq 2$, then $\operatorname{lec}(H)=3$ .

  2. (ii)

If $t=3$, then $3\leq\operatorname{lec}(H)\leq 4$. Moreover
$\operatorname{lec}(H)=4$ if and only if the cycle $C_{5}$ of $H$ does not
contain any diagonal and there are, on $C_{5}$, two vertices each of which is
adjacent to three leaves.

  3. (iii)

If $t\geq 4$, then $\operatorname{lec}(H)=t$ .

###### Proof.

Case 1. First we consider the graph $P_{t}$. As
$\operatorname{diam}(P_{t})\geq 3$, we have
$\operatorname{lec}(P_{t})\geq\max\\{3,t\\}$. A suitable loose colouring of
$P_{1}$ is as follows:
$\varphi(xv)=\varphi(yz)=\varphi(xx_{1})=\varphi(vv_{1})=b$,
$\varphi(xu)=\varphi(vz)=\varphi(zz_{1})=a$, and
$\varphi(uy)=\varphi(uu_{1})=\varphi(yy_{1})=c$.

To get a suitable loose edge-colouring of $P_{2}$ we first take a subgraph
$P_{1}$ of $P_{2}$ and colour its edges as above and then colour the remaining
edges of $P_{2}$ as follows: $\varphi(uu_{2})=a,\varphi(yy_{2})=b$, and
$\varphi(xx_{2})=\varphi(vv_{2})=\varphi(zz_{2})=c$.

There is no loose edge-colouring of $P_{3}$ with three colours. Assume, for a
contrary, that there is one, $\phi$, with colours $a,b$, and $c$. Observe,
that there must be an edge, say, w.l.o.g., $uy$, with $\phi(uy)=b$ and
$\phi(e)\neq b$ for all $e\in\\{ux,vx,vz,yz\\}$. As all three colours have to
be used on the the edges incident to leaves adjacent to $u$ as well as to $y$,
there are two edges $uu_{i}$ and $yy_{j}$ with
$\phi(uu_{i})=\phi(yy_{j})=a\neq b$. Then there is no loose
$u_{i},y_{j}$-path, a contradiction.

The following is a suitable loose colouring of $P_{t},t\geq 3$:
$\varphi(xu)=a,\varphi(xv)=\varphi(yz)=c,\varphi(uv)=b,\varphi(vz)=d$, and
$\varphi(xx_{i})=\varphi(yy_{i})=\varphi(zz_{i})=\varphi(uu_{i})=\varphi(vv_{i})=i,i\in[1,t]$.
Here $\\{a,b,c,d\\}\subseteq[1,t]$. This gives $\operatorname{lec}(P_{3})=4$
and $\operatorname{lec}(P_{t})=t$ for $t\geq 4$. It is easy to see that any
graph $H\subseteq P_{t}$, which is of type (t, P) for $t\geq 4$, has
$\operatorname{lec}(H)=t$.

Case 2. Let $t=3$, $H$ contain no diagonal on its cycle $C_{5}$, and have at
least two vertices adjacent to exactly three leaves. Assume that $H$ has a
loose edge-colouring $\phi$ with three colours $1,2$, and $3$. Evidently, all
these three colours have to appear on $C_{5}$ and let, w.l.o.g., colour $3$ be
unique on $C_{5}$.

Subcase 2.1. The graph $H$ contains on $C_{5}$ two adjacent vertices, say $u$
and $x$, each of which is adjacent to exactly $3$ leaves. Let
$\phi(xx_{i})=\phi(uu_{i})=i$. Colour $3$ cannot appear on the edge $ux$
because otherwise there is no loose $u_{1},x_{1}$-path and we would have a
contradiction. Let $a\in\\{1,2\\}$. If $\\{\phi(xv),\phi(vz)\\}=\\{a,3\\}$
then there is no loose $x_{a},z$-path in $H$; a contradiction. The case
$\\{\phi(xu),\phi(uy)\\}=\\{a,3\\}$ is analogous. Hence, in this case, $H$
requires four colours for its loose edge-colouring. As $H\subseteq P_{3}$ we
can use the loose edge-colouring of $P_{3}$ for $H$.

Subcase 2.2. The graph $H$ contains on $C_{5}$ two non-adjacent vertices, say
$x$ and $y$, each of which is adjacent to exactly $3$ leaves. Let
$\phi(xx_{i})=\phi(yy_{i})=i$. If $\\{\phi(ux),\phi(uy)\\}=\\{a,3\\}$ then
there is no loose $x_{a},y_{a}$-path in $H$; a contradiction. If
$\\{\phi(xv),\phi(vz)\\}=\\{a,3\\}$ then there is no loose $x_{a},z$-path in
$H$; a contradiction. The case when $\\{\phi(yz),\phi(vz)\\}=\\{a,3\\}$ is
symmetric to the latter one. This means that $H$ requires four colours for its
loose edge-colouring. Now we use the loose edge-colouring of $P_{3}$ for $H$.

Case 2.3. Let $H$ contain on $C_{5}$ exactly one vertex, say $v$, adjacent to
exactly three leaves. Then $H$ is subgraph of the graph
$G^{3}=P_{2}\cup\\{v_{3}\\}\cup\\{vv_{3}\\}$, which has a loose edge-colouring
obtained from the colouring of $P_{2}$ extended by $\phi(vv_{3})=a$. This
colouring of $G^{3}$ induces a loose edge-colouring of $H$ with three colours.

Case 3. Let $H$ contain the cycle $C_{5}$ with a diagonal. Then, w.l.o.g., $H$
contains a subgraph $G^{4}=(V(G^{4}),E(G^{4}))$ with vertex set
$V(G^{4})=\\{x,y,z,u,v\\}$ and the edge set
$E(G^{4})=\\{ux,vx,uy,yz,xy,vz\\}$. If we colour the edges of $E(G^{4})$ as
follows $\phi(vx)=\phi(xy)=1$, $\phi(ux)=\phi(yz)=2$, and
$\phi(uy)=\phi(vz)=3$, we can easily extend this colouring to a loose edge-
colouring of $H$ with three colours.

Case 4. If $H$ contains at least two diagonals on its $C_{5}$, then we solve
first the situation for its subgraph with one diagonal as in Case 3, and then
colour arbitrarily the remaining diagonals.

This completes the proof of our Lemma 4. ∎

For the completeness we mention the following:

######  Lemma 5.

If $G_{t}$ is a graph obtained from the cycle $C_{k},k\geq 6$, by attaching
$t$ leaves, $t\geq 1$, to every vertex of $C_{k}$, then
$\operatorname{lec}(G_{t})=\max\\{3,t\\}$.

##  6 2-connected graphs with small circumference

The smallest size among connected graphs $G$ with $\mathrm{cir}(G)=k$ has the
cycle $C_{k}$. The problem of characterization of all ($2$-connected) graphs
$G$ with property $\mathrm{cir}(G)=k$ is very difficult in general but it is
very interesting. As an example of a specific problem of this type is the
problem of characterization of Hamiltonian graphs, see e.g. [18]. There are
also lot of papers devoted to the study of estimations on bounds of the
circumferences of graphs from particular classes. In this section we
characterize all $2$-connected graphs of small circumference.

Denote by $K_{2,s},s\geq 2$, the bipartite graph with vertex set
$V(K_{2,s})=\\{x,y,v_{i},i\in[1,s]\\}$ and edge set
$E(K_{2,s})=\\{xv_{i},yv_{i},i\in[1,s]\\}$.

The graph $K^{\prime}_{2,s}$ is obtained from $K_{2,s}$ by inserting the edge
$xy$. ($D=K^{\prime}_{2,2}$ is also known as a diamond.) The graph
$K^{+}_{2,s}$, $s\geq 3$, is obtained from $K_{2,s}$ by inserting the edge
$v_{2}v_{3}$.

Let $P_{r,s}$, $r\geq 1,s\geq 1$, be the graph with vertex set $V(P_{r,s})$ =
$\\{x,y,z,u_{1},...,u_{r},v_{1},...,v_{s}\\}$ and edge set
$E(P_{r,s})=\\{yz,xu_{i},yu_{i},i\in[1,r],xv_{j},zv_{j},j\in[1,s]\\}$.

The graphs $P^{\prime}_{r,s}$ and $P^{\prime\prime}_{r,s}$, $r\geq 1,s\geq 1$,
come from the graph $P_{r,s}$ by inserting the edge $xy$ and the edges $xy$
and $xz$, respectively.

Note that
$C_{5}=P_{1,1},C^{1}_{5}=P^{\prime}_{1,1},C^{2}_{5}=P^{\prime\prime}_{1,1}$,
$\bar{C}^{2}_{5}=P^{\prime}_{1,1}+u_{1}v_{1}$,
$C^{3}_{5}=P^{\prime\prime}_{1,1}+yv_{1}$,
$\bar{C}^{3}_{5}=\bar{P}^{\prime\prime}_{1,1}+u_{1}v_{1}$,
$C^{4}_{5}=C^{3}_{5}+yv_{1}$, $C^{5}_{5}=K_{5}$, and all denote the cycle
$C_{5}$ of length 5 with $k$ diagonals, $k\in[1,5]$.

######  Theorem 1.

Let $\mathcal{B}_{k}$ be the set of all $2$-connected graphs $G$ with
$\mathrm{cir}(G)=k$. Then

  1. (i)

$\mathcal{B}_{3}=\\{K_{3}=C_{3}\\}$,

  2. (ii)

$\mathcal{B}_{4}=\\{K_{4},K_{2,s},K^{\prime}_{2,s},s\geq 2\\}$.

  3. (iii)

$\mathcal{B}_{5}=\\{\bar{C}^{2}_{5},C^{3}_{5},\bar{C}^{3}_{5},C^{4}_{5},K_{5},K^{+}_{2,l},l\geq
3,P_{r,s},P^{\prime}_{r,s},P^{\prime\prime}_{r,s},r\geq 1,s\geq 1\\}$

###### Proof.

Case (i).This case is easy to see.

Case (ii). First observe, that deleting any edge or any vertex cannot increase
the circumference of a graph.

Suppose that there is a $2$-connected graph $B$ with $\mathrm{cir}(B)=4$ such
that $B\notin\mathcal{B}_{4}$. Let $B$ have the smallest order and then the
smallest size among all counterexamples.

Let $B$ have a vertex $v$ with $\deg_{B}(v)=2$. If both neighbours $w_{1}$ and
$w_{2}$ of $v$ are of degree at least 3, then the subgraph
$B-v\in\mathcal{B}_{4}$. But then either $B\in\mathcal{B}_{4}$ or $B$ contains
a cycle $C_{k}$, $k\geq 5$. A contradiction. If $v$ has a neighbour $w$ of
degree 2, and if $x_{v}$ and $x_{w}$ are other neighbours of $v$ and $w$,
respectively, we replace the $3$-path $x_{v}vwx_{w}$ with the edge
$x_{v}x_{w}$. The resulting graph $\bar{B}$ contains a $2$-cycle and $B$ is
$C_{4}=K_{2,2}$, a contradiction.

Let the minimum degree $\delta(B)\geq 3$. Consider a vertex $v\in V(B)$ with
$\deg_{B}(v)=\delta(B)$. Then the subgraph $B-v$ is connected and each non-
trivial block of it is in $\mathcal{B}_{3}\cup\mathcal{B}_{4}$. One can easily
see that then $B$ contains a cycle of length at least 5, a contradiction.

Case (iii). Assume that there is a $2$-connected graph $B$ with
$\mathrm{cir}(B)=5$ and $B\notin\mathcal{B}_{5}$. Let $B$ have the smallest
order and then the smallest size among all counterexamples. Next we consider
two sub-cases.

Subcase 1. Let $B$ have a vertex $v$ with $\deg_{B}(v)=2$. If both neighbours
of $v$ have degree at least 3, then the subgraph $B-v$ is connected and has
all its non-trivial blocks in
$\mathcal{B}_{3}\cup\mathcal{B}_{4}\cup\mathcal{B}_{5}$. If at least one
neighbour $w$ of $v$ is of degree 2 and if $x_{v}$ and $x_{w}$ are the other
neighbours of $v$ and $w$, respectively, we replace the $3$-path
$x_{v}vwx_{w}$ with the edge $x_{v}x_{w}$. The resulting graph $\bar{B}$
contains a $3$-cycle and $B\in\mathcal{B}_{5}$ or $B$ contains a cycle of
length at least 6, a contradiction.

Subcase 2. Let the minimum degree $\delta(B)\geq 3$. Consider a vertex $v\in
V(B)$ with $\deg_{B}(v)=\delta(B)$. Then the subgraph $B-v$ is connected and
each non-trivial block of it is in
$\mathcal{B}_{3}\cup\mathcal{B}_{4}\cup\mathcal{B}_{5}$. One can easily see
that then $B$ contains a cycle of length at least 6, a contradiction. ∎

##  7 Loose edge-connection of $2$-connected graphs

The complete solution for $2$-connected graphs is given in the following.

######  Theorem 2.

If $G$ is a $2$-connected graph, then
$\mathrm{lec}(G)=\min\\{3,\mathrm{rc}(G)\\}.$

For its proof we first show the following lemma.

######  Lemma 6.

If $G$ is $2$-connected, then $\operatorname{lec}(G)\leq 3$.

###### Proof.

We have to show how to colour the edges of the graph $G$ with colours from the
set $A=\\{a,b,c\\}$ to get a loose edge-connection of $G$. Our procedure
depends on the circumference $\mathrm{cir}(G)$ of $G$.

If $\mathrm{cir}(G)=3$, then we have to colour the graph $K_{3}$, see Theorem
1, the complete graph on three vertices. It will play an important role later.
It is easy to see that $\operatorname{lec}(K_{3})=1$.

If $\mathrm{cir}(G)=4$, then we have to color the graphs from the set
$\mathcal{B}_{4}$, see Theorem 1.

Let the loose edge-colouring of $K_{2,r}$ be as follows: $\varphi(xv_{1})=a$,
$\varphi(xv_{2})=b$, $\varphi(xv_{i})=c,i\in[3,r]$, $\varphi(yv_{1})=b$,
$\varphi(yv_{2})=c$ and $\varphi(yv_{i},)=a,i\in[3,r]$. Observe, that between
any two vertices of $K_{2,r}$, except for the pair $x$ and $y$, there is a
loose (i.e. at least three coloured) path. For the pair $x$ and $y$, if $r\geq
3$, there are three different bi-chromatic $x,y$-paths of length three using
the same three colours.

A loose edge-colouring of the graph $K^{\prime}_{2,r}$ is obtained from that
of $K_{2,r}$ using $\varphi(xy)=a$.

If $\mathrm{cir}(G)=5$, then we have to color the graphs from the set
$\mathcal{B}_{5}$, see Theorem 1. Let the loose edge colouring of $P_{r,s}$ be
defined as follows: $\varphi(xu_{1})=a$, $\varphi(xu_{i})=b$, $i\in[2,r]$,
$\varphi(yz)=c$, $\varphi(xv_{1})=c$, $\varphi(xv_{j})=a,j\in[2,s]$,
$\varphi(yu_{1})=b$, $\varphi(yu_{i})=c$, $i\in[2,r]$, $\varphi(zv_{1})=a$,
$\varphi(zv_{j})=b$, $j\in[2,s]$.

Note that for $r\geq 2$, $s\geq 1$, and any pair of vertices of $P_{r,s}$,
except for the pair $x$ and $y$, there is, in $P_{r,s}$, a loose path using
three colours. For the pair $x$ and $y$ there are three differently bi-colored
$x,y$-paths of length two using the same three colours. The graph
$P^{\prime}_{r,s}$ ($P^{\prime\prime}_{r,s}$), $r\geq 1,s\geq 1$, comes from
the graph $P_{r,s}$ by inserting the edge $xy$ (the edges $xy$ and $xz$,
respectively). The inserted edge in $P^{\prime}_{r,s}$ is coloured with colour
$\varphi(xy)=b$ (The inserted edges in $P^{\prime\prime}_{r,s}$ are colored
with colours $\varphi(xy)=c$ and $\varphi(xz)=b$).

A loose edge-colouring of the graph $K^{+}_{2,r}$ is obtained from that one of
$K_{2,r}$ using colour $a$ for the edge $v_{2}v_{3}$.

The proof that the loose edge-connectivity of the remaining graphs from
$\mathcal{B}_{5}$ is at most 3 is easy and is left to the reader.

If $\mathrm{cir}(G)\geq 6$, we proceed as follows. Colour the edges of the
longest cycle $C$ alternatively by $1,2,3,1,2,3,..$ and other edges of $G$
with colour 1. We distinguish three cases.

Case 1.. For any two vertices $x$ and $y$ on the cycle $C$ there is a path of
length at least three, which is a loose path.

Case 2. If $x\in V(C)$ and $y\notin V(C)$, then there are two paths connecting
$y$ with two vertices $z_{1},z_{2}$ on the cycle $C$. At least one of them is
distinct from $x$, say $z_{1}$. By Case 1 there is a path $L$ on $C$ of length
at least 3 from $z_{1}$ to $x$, which is loose (uses three colors). Now,
taking the path from $z_{1}$ to $y$ (which is vertex disjoint with $L$ except
of vertex $z_{1}$) we obtain a loose $x,y$-path.

Case 3. Let $x,y\notin V(C)$. Similarly as above, there are two vertex
disjoint paths from $x$ to $z_{1}$ and from $y$ to $z_{2}$ with
$z_{1},z_{2}\in V(C),y\neq z_{2}$. As in Case 2 there is a loose path from
$z_{1}$ to $z_{2}$ along the cycle $C$ which leads to a loose path from $x$ to
$y$. ∎

######  Corollary 1.

For every two vertices $x$ and $y$ of a $2$-connected graph $G$ with
$\operatorname{cir}(G)\geq 6$ there is a loose $x,y$-path.

###### Proof.

It follows directly from the proof of Lemma 6. ∎

###### Proof.

Theorem 2. To prove it first observe the following statements.

  1. 1.

$\mathrm{lec}(G)=1$ if and only if $\mathrm{rc}(G)=1$ if and only if $G$ is
complete graph.

  2. 2.

$\mathrm{lec}(G)=2$ if and only if $\mathrm{rc}(G)=2$.

Now for all remaining $2$-connected graphs we have

$3=\mathrm{lec}(G)\leq\mathrm{rc}(G).$

This proves the theorem. ∎

##  8 Loose edge-connection number of complete bipartite graphs

The complete solution for the complete bipartite graphs is given in the
following.

######  Theorem 3.

If $K_{r,s},r\geq s\geq 1$, is a complete bipartite graph, then the following
statements hold:

  1. (i)

$\mathrm{lec}(K_{1,s})=s.$

  2. (ii)

$\mathrm{lec}(K_{r,s})=2$ if $2\leq s\leq r\leq 2^{s}.$

  3. (iii)

$\mathrm{lec}(K_{r,s})=3$ otherwise.

###### Proof.

Let $K_{r,s}$ be a complete bipartite graph with the vertex set
$V(K_{r,s})=X\cup Y$, where $X=\\{x_{1},\dots,x_{r}\\}$ and
$Y=\\{y_{1},\dots,y_{s}\\}$. Let $S_{i}=K_{1,s}$ be the star with the vertex
set $V(S_{i})=\\{x_{i}\\}\cup Y$.

First we consider case (ii).

Suppose that $\phi$ is an edge-colouring of $K_{r,s}$ with two colours $a$ and
$b$. Recall that a path in an edge-coloured graph is called bi-chromatic
(resp. monochromatic) if on its edges exactly two colors (resp. one) are (is)
used.

Let $\mathbf{s}(i)=(a_{i,1},\dots,a_{i,s})$ be a vector of colours of the
edges of the star $S_{i}$ such that $\phi(x_{i}y_{j})=a_{i,j}$ for all
$i\in[1,r]$ and $j\in[1,s]$.

This colouring has the following obvious two properties:

######  Claim 1.

A bi-chromatic $x_{k},x_{l}$-path exists in $K_{r,s}$ if and only if
$\mathbf{s}(k)\neq\mathbf{s}(l)$.

######  Claim 2.

If there is $a_{i,k}\neq a_{i,l}$ in $\mathbf{s}(i)=(a_{i,1},\dots,a_{i,s})$,
then $K_{r,s}$ contains a bi-chromatic $2$-path $y_{k}x_{i}y_{l}$.

Observe, that for $r>2^{s}$ there is no loose edge-coloring of $K_{r,s}$ with
two colours. The reason is that the number of different binary vectors of
dimension $s$ is $2^{s}$. Then, by the pigeonhole principle, there is a pair
of stars, $S_{k}$ and $S_{l}$, with the same vector of colours,
$\mathbf{s}(k)$ and $\mathbf{s}(l)$, respectively, and, by Claim 1, we have no
bi-chromatic path of length two between the pair of vertices $x_{k}$ and
$x_{l}$.

If $2\leq s\leq r\leq 2^{s}$, then there exists a loose edge-colouring of
$K_{r,s}$. It is enough to consider the vectors of colours for the stars
$S_{i},i\in[1,s-1]$, with the following properties: $\phi(x_{i}y_{j})=a$ for
$j\leq i$ and $\phi(x_{i}y_{j})=b$ for $i+1\leq j\leq n$. For $i\in[s,r]$ we
colour the edges of stars $S_{i}$ with such vectors of colours that are
mutually distinct from already chosen ones.

To see that this edge-colouring is loose, observe that Claim 1 ensures us that
for any pair of vertices $x_{k}$ and $x_{l}$, $1\leq k<l\leq r$, there is a
bi-chromatic path of length two between them. The choice of the first $s-1$
vectors of colour ensures the existence of a bi-chromatic $y_{k},y_{l}$-path
of length two for any pair of vertices $y_{k}$ and $y_{l}$ for any pair $k$
and $l$ with $1\leq k<l\leq n$. See Claim 2.

This completes the proof of the theorem for the case (ii).

The proof of theorem in the case (i) follows from Lemma 1 and in the case
(iii) from Lemma 6. ∎

##  9 Graphs with diameter at most 2

To continue we need some more definitions.

The join of two simple graphs $G$ and $H$, written $G\vee H$, is the graph
obtained from the disjoint union $G+H$ by adding the edges $\\{xy:x\in
V(G),y\in V(H)\\}$, see [18].

A nontrivial block $B$ of a graph $G$ is called large if
$\operatorname{cir}(B)\geq 6$ and it is called small if
$2\leq\operatorname{cir}(B)\leq 5$.

Recall that a block $B$ is called trivial if it consists of a cut-edge $e$. In
this case we sometimes will write $B=e$.

It is easy to see that graphs of $\operatorname{diam}(G)\geq 3$ have the loose
edge-connection number $\mathrm{lec}(G)\geq 3$. So the necessary condition for
graphs $G$ to have $\mathrm{lec}(G)=2$ is to have $\operatorname{diam}(G)=2$.
In the previous section we have characterized all complete bipartite graphs
$B$ that have $\mathrm{lec}(B)=2$.

Observe, that if a graph $H$ is a spanning subgraph of a non-complete graph
$G$ and $\mathrm{lec}(H)=2$, then $\mathrm{lec}(G)=2$

Let $G$ and $H$ be graphs with loose edge-connection number two. Then it is
easy to prove that $\mathrm{lec}(G\vee H)=2$, and
$\mathrm{lec}(K_{1}\vee(G+H))=2$.

In Theorem 2 we have mentioned that for a graph $G$ it holds
$\mathrm{lec}(G)=2$ if and only if $\mathrm{rc}(G)=2$. Several classes of
graphs $G$ with $\mathrm{rc}(G)=2$ are known, see e.g. [5], [17], or [16]. For
example, Caro et al. [5] have proved that any non-complete $n$-vertex graph
with minimum degree

$\delta(G)\geq\frac{n}{2}+\log n$

has $\mathrm{rc}(G)=2$.

It is known (cf. [6]) that deciding whether $\mathrm{rc}(G)=2$ is an NP-
complete problem. Hence, the problem to decide whether $\mathrm{lec}(G)=2$ is
also an NP-complete.

The following problem seems to be interesting.

######  Problem 1.

Characterize all connected graphs $G$ with

$\mathrm{lec}(G)=2.$

######  Theorem 4.

Let $G$ be a graph with $\operatorname{diam}(G)\leq 2$. Then

  1. (i)

$\operatorname{lec}(G)=1$ if $G=K_{n},n\geq 2$, and

  2. (ii)

$2\leq\operatorname{lec}(G)\leq\max\\{3,\Delta(C(G))\\}$ otherwise. Moreover,
all three bounds are tight.

###### Proof.

Case (i) is easy.

If $\operatorname{diam}(G)=2$, then G is either $2$-connected or has exactly
one cut-vertex. If it is $2$-connected, then the proof of our theorem follows
from Lemma 6.

If $G$ contains a cut-vertex, $v$, then each block of G is trivial or
$2$-connected. The vertex $v$ is adjacent to all vertices of $V(B)-v$ because
of $\operatorname{diam}(G)=2$. Trivial blocks of $G$ form the graph $C(G)$
which is a star $K_{1,\Delta(C(G))}$. Each nontrivial block $B$ is either a
large block or contains a small block as a spanning subgraph.

The trivial blocks are coloured with distinct colours from $[1,\Delta(C(G)]$.
The remaining blocks are coloured as in Lemma 1 with colours from $[1,3]$.

Next, we need to show that for any pair of two vertices $u$ and $w$ there is
either an edge $uw$, or a bi-chromatic $u,w$-path of length two, or a loose
$u,w$-path.

If the vertices $w$ and $z$ belong to the same block $B$ we are done.

Let $u\in V(B_{i})$ and $w\in V(B_{j})$, where $B_{i}$ and $B_{j}$ are
different non-trivial blocks of $G$. If there is either a loose $u,v$-path in
$B_{i}$ or a loose $w,v$-path in $B_{j}$ then these paths together with the
edge $vu$ or $vw$, respectively, give a loose $u,w$-path. This situation
always appears, with exceptions, when both vertices $u$ and $w$ correspond to
the vertices $x,y$, resp. $z$ of the blocks (graphs) from the families
$\mathcal{B}_{3},\mathcal{B}_{4}$, and $\mathcal{B}_{5}$. But also in these
exceptional cases one can easily find a needed $u,w$-path.

To see, that the bounds $2$ and $3$ are tight, see Theorem 3. For the
tightness of the third bound see the graph $K_{1,s},s\geq 3$. ∎

##  10 Graphs with diameter at least 3

A nontrivial block $B$ of a graph $G$ is called to be of type $P$ (or of type
$Q$, or of type $R$) if it is of type $(t,P)$ (or of type $(t,Q)$, or of type
$(t,R)$, respectively) for some $t\geq 0$.

We recall that a block $B$ of a graph $G$ is small if
$B\in\\{\mathcal{B}_{3}\cup\mathcal{B}_{4}\cup\mathcal{B}_{5}\\}$

A cut-vertex $v$ of an edge-coloured block $B$ of a graph $G$ is called to be
of type $(a,b)$ with respect to $B$ if $deg_{B}(v)=2$, one edge incident with
$v$ is coloured with $a$ and the second one with $b$, $a\neq b$,
$B\in\mathcal{B}_{3}\cup\mathcal{B}_{4}\cup\mathcal{B}_{5}$. Otherwise it is
called universal with respect to $B$.

######  Theorem 5.

Let $G$ be a connected graph with $\operatorname{diam}(G)\geq 3$. The
following statements hold:

  1. (i)

If $G$ is $2$-connected or $0\leq\Delta(C(G))\leq 2$, then
$3\leq\operatorname{lec}(G)\leq 4$.

Furthermore, $\operatorname{lec}(G)=4$ if and only if $G$ contains a block $B$
which is a cycle of length 4 having three distinct vertices
$b_{1},b_{2},b_{3}\in V(B)$ with
$\deg_{C(G)}(b_{1})=\deg_{C(G)}(b_{2})=\deg_{C(G)}(b_{3})=\mathrm{rw}(C(G))=2$,
or

  2. (ii)

If $\Delta(C(G))\geq 3$, then
$\mathrm{rw}(C(G))\leq\operatorname{lec}(G)\leq\mathrm{rw}(C(G))+1$.
Furthermore, $\operatorname{lec}(G)=\mathrm{rw}(C(G))+1$ if and only if

     * (1)

$G$ contains a block $B$ which is a cycle of length 5 having two distinct
vertices $b_{1},b_{2}\in V(B)$ with
$\deg_{C(G)}(b_{1})=\deg_{C(G)}(b_{2})=\mathrm{rw}(C(G))=3$, or

     * (2)

$G$ contains a block $B$ which is a cycle of length 4 and
$\deg_{C(G)}(b)=\mathrm{rw}(C(G))=3$ for a vertex $b\in V(B)$, or

     * (3)

$G$ contains a block $B$ which is a cycle of length 3 having two distinct
vertices $b_{1},b_{2}\in V(B)$ with $\deg_{C(G)}(b_{1})+\deg_{C(G)}(b_{2})\geq
2\mathrm{rw}(C(G))-1$, or

     * (4)

$G$ contains a block $B$ which is a diamond $D$, $V(D)=\\{x,v,y,w\\}$,
$\mathrm{rw}(C(G))=3$, and $\deg_{C(G)}(x)+\deg_{C(G)}(y)=6$ or $\sum_{b\in
V(B)}\deg_{C(G)}(b)\geq 11$.

###### Proof.

Part 1. Colouring. Let
$\mathcal{D}=\\{K_{3},C_{4},D,K_{4},C_{5},C_{5}^{1},C_{5}^{2},\bar{C}_{5}^{2},C_{5}^{3},\bar{C}_{5}^{3},C_{5}^{4},K_{5}\\}$
be a set of specific small blocks. Recall that any large block and any small
block, other than that from $\mathcal{D}$, has a loose edge-colouring with
three colours. Between any two distinct vertices of large blocks and any two
vertices of small blocks other than that from $\mathcal{D}$, except two
specific $x$ and $y$ of small blocks, there exists a loose path (Recall, that
a path is loose if has length at least three, which edges are coloured with at
least three colours). The vertices $x$ and $y$ are connected with three
mutually distinct bi-chromatic $x,y$-path. See the proof of Lemma 6.

Our colouring follows the properties of the block-cutpoint graph $B(G)$ of
$G$. Choose a vertex of $B(G)$ corresponding to a block $B$ as a root. We
colour edges of the blocks from this root to the leaf blocks. First we colour
edges of $B$ as described in Lemma 6 if $B$ is $2$-connected and with colour 1
if $B$ is trivial. If $B$ is trivial (i.e. $B=\\{e\\}$, where $e$ is an edge)
we colour all edges of the component of $C(G)$ containing the edge $e$
according to the method used in the proof of Lemma 1.

General Step: Let $v$ be a cut vertex on $B$ and let
$B_{1},\dots,B_{k},S_{1},\dots,S_{l},T_{1},\dots,T_{r}$ be other blocks
containing $v$ as cut-vertex, where $B_{i}$, for $i\in[1,k]$, is a large
block, $S_{j}$, for $j\in[1,l]$, is a small block, and $T_{s}$, for
$s\in[1,r]$, is a trivial block. First we colour large blocks, next small
blocks different from blocks from $\mathcal{D}$, then small blocks from
$\mathcal{D}$, and, finally, trivial blocks.

We distinguish three cases.

Case 1. Let $deg_{B}(v)=1$ and $\varphi(wv)=a$ be a colour of the unique edge
$wv$ in $B$. Then for every $i\in[1,k]$ the edges of the block $B_{i}$ are
coloured with colours from the color set $\\{a,b,c\\}$ as stated in Corollary
1.

If $S_{j}$, $j\in[1,l]$, is a small block from
$(\mathcal{B}_{3}\cup\mathcal{B}_{4}\cup\mathcal{B}_{5})\setminus\mathcal{D}$
and $\deg_{S_{j}}(v)=2$, then the edges incident to $v$ in $S_{j}$ are colored
with colours from $\\{a,b,c\\}$ so that the vertex $v$ becomes of type
$(b,c)$, where $b\neq a\neq c$. Next we finish the colouring of edges of
$S_{j}$ as described in the proof of Lemma 6. If $\deg_{S_{j}}(v)\geq 3$, then
we colour $S_{j}$ directly as in Lemma 6.

If $S_{j}\in\mathcal{D}$, then its edges are coloured together with all
trivial blocks (edges) incident to the vertices of the block $S_{j}$. In this
case we colour the subgraph $H$ of type $(t,O)$ for $t\geq 1$ and
$O\in\\{P,Q,R\\}$ as described in Lemmas 4, 3, and 2, respectively, taking
into consideration the following three facts: (i) The edges of the longest
cycle of $H$ incident with the vertex $v$ have to obtain in $H$ the colours
$b$ and $c$. (ii) Some of edges of $H$ at $v$ can already be coloured (This
can happen if the block $B$ is trivial, or there are several blocks of types
from $\\{P,Q,R\\}$ at the considered cut vertex $v$). (iii) If $H$ is of type
$(1,R)$, we colour its edges with three colours as in $R_{1}$ because
$H\subset R_{1}$.

If $S_{j}\in\mathcal{D}$ and there no trivial blocks incident to vertices of
$S_{j}$, i.e. $S_{j}$ is subgraph of type $(0,O)$, we colour its edges as in
Lemma 6 except of the case when $S_{j}=C_{3}=K_{3}$. In the later case the
edges of $C_{3}$ are coloured with three distinct colours.

Let there be trivial blocks at $v$, i.e., $r\geq 1$. If this block is a part
of a subgraph of type $O\in\\{P,Q,R\\}$ at $v$, then all trivial blocks are
coloured as a part of the colouring of the first considered subgraph of type
$O$. If there is no subgraph of type $O\in\\{P,Q,R\\}$ at $v$, then the edges
of all trivial blocks (i.e. edges) are part of a component of $C(G)$. In this
case we colour all edges of this component as described in the proof of Lemma
1.

Case 2. Let $deg_{B}(v)=2$ and the vertex $v$ be of type $(a,b)$. Then the
large block $B_{i}$, for any $i\in[1,k]$ is coloured with colours from the
color set $\\{a,b,c\\}$ as in the proof of Lemma 6.

The block $S_{j}$, for any $j\in[1,l]$, $S_{j}\notin\mathcal{D}$, is handled
as a large block if $v$ has, in it, degree at least three, or such that the
vertex $v$ becomes of type $(a,b)$ in the colouring of $S_{j}$, if $v$ has
degree two. If $S_{j}\in\mathcal{D}$ is a subgraph $H$ of type
$O\in\\{P,Q,R\\}$, then we consider the subgraph $H$ of type $O$ and colour it
as described in Case 1.

Trivial blocks $T_{s}$ are handled in the same way as in Case 1.

Case 3. Let $deg_{B}(v)\geq 3$. Our colouring in this case continues as in
Case 2 keeping in mind that all small blocks $S_{j}$, $j\in[1,l]$, have to be
colored in such a way that the cut-vertex $v$ becomes of type $(a,b)$ if it is
of degree two in $S_{j}$.

If all blocks containing $v$ as a cut-vertex are colored, $v$ is called ready.

To continue in the colouring of $G$ a next, not ready, cut-vertex from a
colored block is chosen.

The procedure of colouring finishes if every cut vertex of $G$ is ready.

Observe, see Lemmas 1, 2, 3, 4 and 6, that our colouring uses colours from the
set $M=[1,\mathrm{rw}(C(G))]$ except for the cases listed in our Theorem 5.
These exceptional cases use the colours from the colour set $M^{*}=[1,4]$ if
$G$ contains a subgraph $H$ of type $Q$ described in Lemma 3 (i) and from the
colour set $M^{\prime}=[1,\mathrm{rw}(C(G))+1]$ if $G$ contains subgraphs $H$
of type $O\in\\{P,Q,R\\}$ described in the Lemmas 4 (ii), 3 (ii), and 2 (iii),
respectively.

Part 2. Loose connectivity. To finish the proof of the theorem it is necessary
to show that any two distinct vertices $w_{1}$ and $w_{2}$ are connected by an
edge $w_{1}w_{2}$, or bi-chromatic $w_{1},w_{2}$-path of length 2, or a loose
(with at least three different colours) $w_{1},w_{2}$-path of length at least
3. Such a path exists if both $w_{1}$ and $w_{2}$ belong to the same block, to
the same component of $C(G)$, or to the same subgraph $H$ of type
$O\in\\{P,Q,R\\}$.

If there is an $w_{1},w_{2}$-path going through two vertices, say $u_{1}$ and
$u_{2}$, of a large block or of a small block, then the part between them can
be replaced by a loose $u_{1},u_{2}$-path lying inside the block.

Hence, it is sufficient to show the existence of such a loose
$w_{1},w_{2}$-path for any two blocks $D_{1}$ and $D_{2}$ with a common cut-
vertex $z$, $w_{1}\in V(D_{1})$ and $w_{2}\in V(D_{2})$, $w_{1}\neq z\neq
w_{2}$.

If the block $D_{1}$ is large, then there is a loose $w_{1},z$-path in
$D_{1}$, which together with a $z,w_{2}$-path in $D_{2}$ gives a needed loose
$w_{1},w_{2}$-path.

Let the block $D_{1}$ be small and $D_{2}$ be either small or trivial. If the
vertex $w_{1}$ is not corresponding to any of the vertices $x$ and $y$ of
$D_{1}\in\\{K_{2,s},K^{\prime}_{2,s},K^{+}_{2,s}\\}$ or to any of the vertices
$x,y$ and $z$ of
$D_{1}\in\\{P_{2,s},P^{\prime}_{2,s},P^{\prime\prime}_{2,s}\\}$, respectively,
then there is, in $D_{1}$, a loose $w_{1},z$-path. This path together with a
$z,w_{2}$-path gives a required loose $w_{1},w_{2}$-path.

If the vertex $w_{1}$ and the vertex $w_{2}$ are corresponding to some of the
above mentioned vertices $x,y$, or $z$ of $D_{1}$ and of $D_{2}$,
respectively, Then one can easy recognise in $G$ a loose $w_{1},w_{2}$-path of
length 3 or 4.

∎

Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

Acknowledgements

The research of all three authors was supported in part by the DAAD-PPP
project ”Colourings and connection in graphs” with project-ID 57210296.

The work of the second author was supported by the Slovak Research and
Development Agency under the contract No. APVV-19-0153 and by the Slovak VEGA
grant 1/0574/21.

## References

  * [1] S. A. van Aardt, C. Brause, A. P. Burger, M. Frick, A. Kemnitz, and I. Schiermeyer, _Proper connection and size of graphs_ , Discrete Math. 340 (2017) 2673–2677.
  * [2] V. Borozan, S. Fujita, A. Gerek, C. Magnant, Y. Manoussakis, L. Montero, and Z. Tuza, _Proper connection of graphs_ , Discrete Math. 312 (2012) 2550–2560.
  * [3] Ch. Brause, S. Jendrol’, I. Schiermeyer, _Odd connection and odd vertex connection of graphs_ , Discrete Math. 341 (2018) 3500-3512.
  * [4] Ch. Brause, S. Jendrol’, I. Schiermeyer, _From colourful to rainbow paths in graphs: Colouring the vertices_ , Graphs Combin. 37 (2021) 1823–1839
  * [5] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, _On the rainbow connection_ , Electron. J. Combin. 15 (2008) R57.
  * [6] S. Chakraborty, E. Fischer, A. Matsliak, R. Yuster, _Hardness and algorithms for rainbow connectivity_ , J. Combin. Optim. 21 (2011) 330–347.
  * [7] L. S. Chandran, A. Das, D. Rajendraprasad, and N. M. Varma, _Rainbow connection number and connected dominating sets_ , J. Graph Theory 71 (2012) 206–218.
  * [8] G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang, _Rainbow connection in graphs_ , Math. Bohemica 133 (2008) 85–98.
  * [9] J. Czap, _Edge looseness of plane graphs_ , Ars Math. Contemp. 9 (2015) 285–296.
  * [10] J. Czap and S. Jendrol’, _Facially-constrained colorings of plane graphs: A survey_ , Discrete Math., 340 (2017) 2691–2703.
  * [11] J. Czap, S. Jendrol’, and J. Valiska, _Conflict-free connections of graphs_ , Discuss. Math. Graph Theory 38 (2018) 911–920.
  * [12] P. Holub, Z. Ryjáček, and I. Schiermeyer, _On forbidden subgraphs and rainbow connection in graphs with minimum degree $2$_, Discrete Math. 338 (2015) 1–8.
  * [13] P. Holub, Z. Ryjáček, I. Schiermeyer, and P. Vrana, _Rainbow connection and forbidden subgraphs_ , Discrete Math. 338 (2015) 1706–1713.
  * [14] P. Holub, Z. Ryjáček, I. Schiermeyer, and P. Vrana, _Characterizing forbidden pairs for rainbow connection in graphs with minimum degree $2$_, Discrete Math. 339 (2016) 1058–1068.
  * [15] X. Li, Y. Shi, and Y. Sun, _Rainbow connections of graphs: A survey_ , Graphs Combin. 29 (2013) 1–38.
  * [16] A. Kemnitz, I. Schiermeyer, _Graphs with rainbow connection number two_ , Discuss. Math. Graph Theory 31 (2011) 313–320.
  * [17] S. Negami, _Looseness ranges of triangulations on closed surfaces_ , Discrete Math. 303 (2005) 167–174.
  * [18] D. B. West, _Introduction to Graph Theory_ , Prentice Hall, 2000.