---
abstract: |
    A path in an edge-coloured graph is called *rainbow path* if its edges receive pairwise distinct colours. An edge-coloured graph is said to be *rainbow connected* if any two distinct vertices of the graph are connected by a rainbow path. The minimum $k$ for which there exists such an edge-colouring is the rainbow connection number $rc(G)$ of $G.$ Recently, Bau et al. @BJJKM2018 introduced this concept with the additional requirement that the edge-colouring must be proper. The *proper rainbow connection number* of $G$, denoted by $prc(G)$, is the minimum number of colours needed in order to make it properly rainbow connected.

    In this paper we first prove an improved upper bound $prc(G) \leq n$ for every connected graph $G$ of order $n \geq 3.$ Next we show that the difference $prc(G) - rc(G)$ can be arbitrarily large. Finally, we present several sufficient conditions for graph classes satisfying $prc(G) = \chi'(G).$

    **Keywords:** edge-colouring; proper; rainbow connection number; proper rainbow connection number;\
    **AMS subject classification 2010:** 05C15, 05C40, 05C07.\
author:
- |
     Trung Duy Doan$^{1}$ , Ingo Schiermeyer$^{2}$\
    $^{1}$ School of Applied Mathematics and Informatics\
    Hanoi University of Science and Technology, Hanoi, Vietnam\
    $^{2}$Institut für Diskrete Mathematik und Algebra\
    Technische Universität Bergakademie Freiberg\
    09596 Freiberg, Germany\
    <span>Email: cwilliams@example.net, cwilliams@example.net</span>\
title: '**Proper rainbow connection number of graphs**'
---

Introduction
============

We use @West2001 for terminology and notation not defined here and consider only simple, finite and undirected graphs. Let $G$ be a graph. We denote by $V(G), E(G), n, m, \Delta(G),$ $diam(G)$ the vertex set, the edge set, number of vertices, number of edges, maximum degree, and diameter of $G$, respectively. Let $K_n,C_n,P_n$ be a complete graph, a cycle and a path on $n$ vertices, respectively. By $N_G(u)$ we denote the set of neighbours of a vertex $u\in V(G)$ and by $d(u)$ its degree $G$. Let us denote by $d(u,v)$ and $d(uPv)$ the distance between two vertices $u,v$ and the length of a $u,v$-path $P$, respectively. For each integer $n\geq4$, the wheel is defined as $W_n=C_n+K_1$, the join of $C_n$ and $K_1.$ For simplifying notation, let $[k]$ be the set $\lbrace 1,2,\ldots,k\rbrace$ for some positive integer $k$.

Let $c: E(G) \rightarrow [k]$ be an edge-colouring of $G.$ If adjacent edges of $G$ receive different colours by $c$, then $c$ is a *proper colouring*. The smallest number of colours needed in a proper colouring of $G$, denoted by $\chi'(G)$, is called the *chromatic index* of $G$. Vizing et al. @Vizing1964 proved that for any graph $G$, $\chi'(G)$ is either its maximum degree $\Delta(G)$ or $\Delta(G)+1$. If $\chi'(G)=\Delta(G)$, then $G$ is in *class 1*. Otherwise, $G$ is in *class 2*.

A path $P$ in an edge-coloured graph $G$ is called a *rainbow path* if its edges have different colours. An edge-coloured graph $G$ is *rainbow connected* if every two vertices are connected by at least one rainbow path in $G$. For a connected graph $G$, the *rainbow connection number* of $G$, denoted by $rc(G)$, is defined as the smallest number of colours required to make it rainbow connected. The concept of rainbow connection was first introduced by Chartrand et al. @Chartrand2008 and well-studied since then. Readers who are interested in this topic are referred to @LiSh2013 [@Li2012].

As an extension of proper colouring and motivated by rainbow connections of graphs, Bau et al. @BJJKM2018 introduced the concept of proper rainbow connections in connected graphs. Let $G$ be a nontrivial connected graph. The proper edge-coloured graph $G$ is said to be *properly rainbow connected* if any two vertices $u,v\in V(G)$ are connected by a rainbow path. The *proper rainbow connection number* $prc(G)$ of a connected graph $G$ is the smallest number of colours needed to colour $G$ properly rainbow connected. By the definition above, if an edge-coloured graph $G$ is properly rainbow connected, then $G$ is properly coloured and rainbow connected. Hence, the lower bound of the proper rainbow connection number was obtained by the following proposition.

\[Bau et al. @BJJKM2018\] \[Prop\_Lower\_Bau\] Let $G$ be a connected graph. Then $$diam(G)\leq rc(G)\leq prc(G)$$ and $$\chi'(G)\leq prc(G).$$

On the other hand, if every edge of $G$ receives a distinct colour from $[m]$, where $m$ is the number edges of $G$, then $G$ is properly rainbow connected. By using Proposition \[Prop\_Lower\_Bau\] and Vizing's Theorem in @Vizing1964, the proper rainbow connection number of an arbitrary connected graph is bounded as follows.

\[Cor\_Bounded\] Let $G$ be a connected graph of size $m$. Then $$\max\lbrace rc(G),\chi'(G)\rbrace\leq prc(G)\leq m.$$

The authors in @JLLM2019 determined some graphs with large proper rainbow connection number. First of all, they characterized all graphs whose proper connection numbers equal their size.

\[Jiang et al. @JLLM2019\] \[Thm\_Jiang\_prc\_size\] Let $G$ be a connected graph of size $m$. Then $prc(G)=m$ if and only if $G$ is a tree or $K_3$.

After that, they also classified connected graphs whose proper connection numbers are close to the maximum possible value. Let $\mathcal{H'}$ and $\mathcal{H''}$ be two graph classes as shown in Figure \[Fig\_Jiang\_1\], where the order of $H'\in\mathcal{H'}$ is at least $4$ and the order of $H''\in\mathcal{H''}$ is at least $5$, respectively.

<span>0.45</span>

(v1) at (0,0) ; (v2) at (-1,0.5) ; (v3) at (-1,-0.5) ; (v4) at (3,0) ; (v1)–(v2)–(v3)–(v1); (v1)–(v4); at (1,-1.5) <span>$H'$</span>;

<span>0.45</span>

(v1) at (0,0) ; (v2) at (-1,0.5) ; (v3) at (-1,-0.5) ; (v6) at (1,1) ; (v7) at (1,-1) ; (v4) at (1,0.6) ; (v5) at (1,-0.6) ; at (0,-1.5) <span>$H'$</span>; (v1)–(v2)–(v3)–(v1); (v1)–(v4); (v1)–(v5); (v1)–(v7); (v1)–(v6); (v4)–(v5);

\[Jiang et al. @JLLM2019\] \[Thm\_Jiang\_prc\_close\_size\] If $G$ is a connected graph of size $m$, then $prc(G)=m-1$ if and only if $G\in\mathcal{H'}$ or $G\in\mathcal{H''}$.

Next, the proper rainbow connection numbers of special graphs were considered by Bau et al. @BJJKM2018 and Jiang et al. @JLLM2019.

\[Bau et al. @BJJKM2018\] \[Thm\_Bau\_Compl\] For each integer $n \geq 2$, $$prc(K_n)=\chi'(K_n)=
\begin{cases}
n-1, &\mbox{if } n \mbox{ is even} \\
n, &\mbox{if } n \mbox{ is odd}
\end{cases}$$

\[Jiang et al. @JLLM2019\] \[Cor\_Jiang\_Cyc\] For each interger $n\geq4$, $prc(C_n)=\lceil\frac{n}{2}\rceil.$

Chartrand et al. @Chartrand2008 determined the rainbow connection numbers of complete graphs.

\[Chartrand et al. @Chartrand2008\] \[Pro\_Chartrand\_Compl\] Let $n\geq2$ be an integer. Then $rc(K_n)=1.$

By Theorem \[Thm\_Bau\_Compl\] and Proposition \[Pro\_Chartrand\_Compl\], it can be readily seen that the difference $prc(G)-rc(G)$ can be arbitrarily large.

The *cartesian product* of two graphs $G$ and $H$ written $G\square H$ is the graph with vertex set $V(G)\times V(H)$ specified by putting $(u_1,u_2)$ adjacent to $(v_1,v_2)$ if and only if (1) $u_1=u_2$ and $v_1v_2\in E(H)$, or (2) $v_1=v_2$ and $u_1u_2\in E(G).$ Bau et al. @BJJKM2018 and Jiang et al. @JLLM2019 determined proper connection numbers of cartesian products by the following results.

\[Bau et al. @BJJKM2018\] \[Pro\_Bau\_Carte\] Let $n,p_1,\ldots,p_n>1$ be integers and\
$G=K_{p_1}\square\ldots\square K_{p_n}.$ Then $$\sum_{i=1}^{n}(p_i-1)\leq prc(G)\leq\sum_{i=1}^{n}\chi'(K_{p_i})$$

\[Jiang et al. @JLLM2019\] \[Thm\_Jiang\_Carte\] Suppose that $n\geq1$, and $p_1,\ldots,p_n>1$ are integers. If $G=K_{p_1}\square\ldots\square K_{p_n}$, then $prc(G)=\chi'(G)$.

Upper bounds
============

In this section we will show improved upper bounds for the proper rainbow connection number of graphs.

The concept of rainbow connection was first introduced by Chartrand et al. @Chartrand2008. Moreover, they gave the relation between rainbow connection number of a connected graph and rainbow connection number of its spanning tree as follows.

\[Chartrand et al. @Chartrand2008\] \[Prop\_Chartrand\_rc\] Let $G$ be a connected graph and $T$ be a spanning tree of $G$. Then $rc(G)\leq rc(T)$.

By Proposition \[Prop\_Chartrand\_rc\], it can be readily seen that if $G$ has $n$ vertices, then $rc(G)\leq n-1$. Moreover, by Theorem \[Thm\_Bau\_Compl\] and Corollary \[Cor\_Jiang\_Cyc\], proper connection numbers of complete graphs and cycles do not exceed their number of vertices. These facts are our motivation to improve the upper bound for the proper rainbow connection number as follows.

\(w) at (0,0) ; at (0,0) <span>$w$</span>; (w1) at (-2.5,-3) ; at (-2.5,-3) <span>$w_1$</span>; (w2) at (-1,-3) ; at (-1,-3) <span>$w_2$</span>; at (-0.5,-3) ; at (0,-3) ; at (0.5,-3) ; at (1,-3) ; (w\_max) at (2.5,-3) ; at (2.5,-3) <span>$w_{\bigtriangleup(G)}$</span>; (w1)–(w)–(w2); (w\_max)–(w); at (-1.2,-1.5) <span>$1$</span>; at (-0.4,-1.5) <span>$2$</span>; at (1.2,-1.5) <span>$\bigtriangleup(G)$</span>;

\[Thm\_upper\_bound\] Let $G$ be a nontrivial, connected graph of order $n$ and maximum degree $\Delta(G)$. Then $$\max\lbrace \Delta(G),diam(G)\rbrace\leq prc(G)\leq \chi'(G)+(n-1-\bigtriangleup(G))=
\begin{cases}
n,\mbox{ if }G\mbox{ is class 2}\\
n-1,\mbox{ if }G\mbox{ is class 1}
\end{cases}$$

\[proof\_thm\_upper\_bound\] Since $\Delta(G)\leq\chi'(G)$ by Vizing's Theorem in @Vizing1964 and $diam(G)\leq rc(G)$ by Chartrand et al. @Chartrand2008, the lower bound is easily obtained.

Next, we consider the upper bound. Since $G$ has maximum degree $\bigtriangleup(G)$, there exists a vertex $w\in V(G)$ such that $d_G(w)=\bigtriangleup(G)$. Let $N_G(w)=\lbrace w_1,w_2,...,w_{\bigtriangleup(G)}\rbrace$ be the neighbour set of $w\in V(G)$. We construct a tree $T \cong K_{1,\bigtriangleup(G)}$, which consists of the vertex $w$ as a root of the tree $K_{1,\bigtriangleup(G)}$ and all the vertices in the set $N_G(w)$. Let $c$ be a proper edge-colouring of $G$ with $\chi'(G)$ colours $\{1, 2, \ldots, \chi'(G)\}$. We may assume that the edges of $T$ have colours $1, 2, \ldots, \Delta(G)$. Since $G$ is connected, we can extend the tree $T$ to a spanning tree $T'$ of $G$ by properly adding $n-1-\Delta(G)$ edges. Now we recolour these $n-1-\Delta(G)$ edges by using $n-1-\Delta(G)$ new colours. This leads to an proper edge-colouring $c'$ of $G,$ since every new colour is used exactly once. Moreover, the tree $T'$ is rainbow coloured, which shows that $G$ is properly rainbow-connected.

By using Vizing's Theorem in @Vizing1964, $prc(G)\leq n$, if $G$ is class $2$ or $prc(G)\leq n-1$, if $G$ is class $1$. We obtain the result.

Now, we improve the upper bound by requiring a structural condition.

\[Propo\_improve\_upper\_bound\] Let $G$ be a connected graph with maximum degree $\Delta(G)\leq n-2$ and $w\in V(G)$ such that $d(w)=\Delta(G)$. If there is a Hamiltonian cycle in $G-N[w]$, then $prc(G)\leq\frac{n+\Delta(G)}{2}+1$.

Suppose that $G$ has a vertex $w$ with $d(w)=\Delta(G)$ and there is a Hamiltonian cycle, say $C$, in $G-N[w]$. Let us colour all the edges of $E(G)\setminus E(C)$ by $c:1\rightarrow[\chi'(G)]$ in order to make it a proper colouring. Next, we continue to colour all remaining edges of $C$ with $\lceil\frac{\vert V(C)\vert}{2}\rceil$ new colours. It can be readily seen that $G$ is properly rainbow connected using $\chi'(G)+\bigl\lceil\frac{\vert V(C)\vert}{2}\bigr\rceil$ colours. Since $\Delta(G)\leq n-2$, it can be readily seen that $$prc(G)\leq\Delta(G)+1+\bigl\lceil\frac{n-1-\Delta(G)}{2}\bigr\rceil\leq\frac{n+\Delta(G)}{2}+1.$$

The result is obtained.

Estimating the difference $prc(G) - rc(G)$
==========================================

Next observe that

$$0 \leq prc(G) - rc(G) \leq n-1$$

for all connected graphs $G,$ where the upper bound is attained for $K_n$ if $n$ is odd. We now extend this observation as follows.

Let $G$ be a connected graph of order $n \geq 2$ with clique number $\omega(G) \geq \frac{n+1}{2}.$ Then $$prc(G) - rc(G) \geq 2\omega(G)-n-1.$$

If $\omega(G)=n,$ then the inequality is true. Hence we may assume that $\frac{n+1}{2} \leq \omega(G) \leq n-1.$ First observe that $rc(G) \leq n+1-\omega(G).$ To see this, take a clique of size $\omega(G)$ and colour all edges between its vertices by one colour. Next we add $n-\omega(G)$ edges to obtain a spanning subgraph of $G.$ We colour each edge by a new colour and can colour all remaining edges arbitrarily. Then this colouring makes $G$ rainbow connected. Since $G$ is connected and $\omega(G) \leq n-1,$ we deduce that $\Delta(G) \geq \omega(G).$ Hence by Theorem 2.2 we obtain $prc(G) \geq \omega(G).$ Now the inequality follows.

Next we analyse the values of $prc(G)$ and $rc(G)$ for graphs with respect to their minimum degree.

Let $G$ be a connected graph of order $n \geq 3$ and minimum degree $\delta = \delta(G). If$

1.  $\delta \geq 3,$ then $rc(G) \leq \frac{3n}{4}$ @S2009,

2.  $\delta \geq 4,$ then $rc(G) \leq \frac{3n}{\delta + 1}+3$ @CDRV2012.

Now observe that $\delta \geq \frac{3n}{\delta +1}+3$ if $\delta \geq 1 + \sqrt{3n+4}.$ With $prc(G) \geq \chi'(G) \geq \Delta(G) \geq \delta(G)$ we thus obtain

Let $G$ be a connected graph of order $n$ and with $\delta(G) \geq 1 + \sqrt{3n+4}.$ Then

$$prc(G) - rc(G) \geq \delta - (\frac{3n}{\delta +1}+3)$$

Further observe that

$$0 \leq prc(G) - \chi'(G) \leq (n-1)-2= n-3$$

for all connected graphs with $n \geq 3,$ where the upper bound is attained for the path $P_n.$

Since $prc(G) \geq max\{rc(G),\chi'(G)\}$ by Corollary 1.2, it is natural to ask whether the difference $prc(G) - max\{rc(G),\chi'(G)\}$ is unbounded as well. In our next Theorem we show that the difference $prc(G) - rc(G)$ can be arbitrarily large.

\[Thm\_exist\_graph\_Delta\_Diam\] Let $k,t$ be two integers, where $k\geq t\geq1$. There always exists a connected graph $G_{k,t}$ with $\Delta(G)=2t^2+1$ and $diam(G)=2t^2+1+k$ such that $prc(G)\geq rc(G)+t$.

(u1) at (0,0) ; at (0,0) <span>$v_1$</span>; (u2) at (0,-3) ; at (0,-3) <span>$v_2$</span>; (u3) at (1.5,-1.5) ; at (1.5,-1.5) <span>$u_3$</span>; (u4) at (3.5,-1.5) ; at (3.5,-1.5) <span>$u_4$</span>; (u5) at (5.5,-1.5) ; at (5.5,-1.5) <span>$u_5$</span>; (u6) at (7.5,-1.5) ; at (7.5,-1.5) <span>$u_6$</span>;

(u1)–(u2)–(u3)–(u4)–(u5)–(u6); (u1)–(u3); at (0,-1.5) <span>$2$</span>; at (0.75,-0.75) <span>$1$</span>; at (0.75,-2.25) <span>$3$</span>; at (2.5,-1.5) <span>$2$</span>; at (4.5,-1.5) <span>$4$</span>; at (6.5,-1.5) <span>$5$</span>;

Firstly, if $k=t=1$, then we take a connected graph with $\Delta(G)=3$ and $diam(G)=4$ as shown in Figure \[Figure\_3\]. Clearly, $rc(G)=4$ and $prc(G)=5=rc(G)+t$.

Now, we consider $t\geq2$. Let $W_{2t^2}$ be a wheel consisting of a cycle $C=v_1\ldots v_{2t^2}v_1$ and a center vertex $v$. Let $G$ be a connected graph constructed from $W_{2t^2}$ and a path $P=u_{2t^2+1}\ldots u_{4t^2+1+k}$ of order $2t^2+1+k$ by identifying $v$ and $u_{2t^2+1}$ as shown in Figure \[Figure\_4\]. It can be readily seen that $\Delta(G)=2t^2+1$ and $diam(G)=2t^2+1+k$. Hence, $rc(G)\geq 2t^2+1+k$. Let us define a colouring $c$ with $2t^2+1+k$ colours to colour all the edges of $G$ as follows. $$c(e)=
\begin{cases}
1 & \mbox{if} \hspace{0.5em} e=vv_i, \forall i\in[2t^2]\\
i+1-2t^2 & \mbox{if} \hspace{0.5em} e=u_iu_{i+1}, \forall i\in[2t^2+1,4t^2+k]\\
i & \mbox{if} \hspace{0.5em} e=v_iv_{i+1}, \forall i\in[t^2]\\
i-t^2 & \mbox{if} \hspace{0.5em} e=v_iv_{i+1},\forall i\in[t^2+1,2t^2-1]\\
t^2 & \mbox{if}\hspace{0.5em} e=v_{2t^2}v_1
\end{cases}$$ It can be readily seen that $G$ is rainbow connected with $2t^2+1+k$ colours. Thus, $rc(G)\leq 2t^2+1+k$. So we deduce that $rc(G)=2t^2+1+k$.

Next, we show that $prc(G)\geq 2t^2+1+k+t$.

Suppose that $prc(G)\leq 2t^2+k+t$. Then there is a colouring $c$ with $2t^2+k+t$ colours which makes $G$ properly rainbow connected. Since $P$ is the only path from $u_{2t^2+1}$ to $u_{4t^2+1+k},$ $P$ is a rainbow path. Hence we may assume that its $2t^2+k$ edges are coloured with the colours $1, 2, \ldots, 2t^2+k.$ Since $G$ is properly rainbow connected, all the edges that are incident to $v$ receive distinct colours. Moreover, every rainbow path from $u_{4t^2+1+k}$ to a vertex $v_i, 1 \leq i \leq 2t^2,$ uses exactly one edge $vv_j,$ whose colour is distinct from $1, 2, \ldots, 2t^2+k.$ Hence we may assume that $p$ of these edges, where $1 \leq p \leq t,$ have a colour from the set $2t^2+k+1, \ldots, 2t^2+k+t.$ Suppose first that $p=1.$ We may assume that $vv_1$ has the only colour from the set $2t^2+k+1, \ldots, 2t^2+k+t.$ Then any rainbow path from $v_{t^2+1}$ to $u_{4t^2+1+k}$ has $t^2 + 1 + (2t^2+k) > 2t^2+k+t$ edges, a contradiction. Next suppose that $p \geq 2.$ So there are $p$ integers $1 \leq i_1 < i_2 < \ldots < i_p \leq 2t^2$ such that the edges $vv_{i_1}, \ldots, vv_{i_p}$ have these $p$ colours. So there is a partition of the cycle $C$ into $p$ paths, each connecting $v_{i_j}$ with $v_{i_{j+1}}$ along the cycle of length $|i_{+1}-i_j|$ (modulo $2t^2$). Hence the longest of these $p$ paths has length at least $\frac{2t^2}{p} \geq \frac{2t^2}{t} = 2t.$ We may assume that the path from $v_{i_1}$ to $v_{i_2}$ has length at least $2t$ and that $i_1=1.$ Then any rainbow path from $v_{t+1}$ to $u_{4t^2+1+k}$ has at least $t+1+2t^2+k$ edges, a contradiction.

\(v) at (0,0) ; at (0,0) <span>$v\equiv u_{2t^2+1}$</span>; (v1) at (<span>45\*4.5:2</span>) ; at (<span>45\*4.5:2</span>) <span>$v_{2t^2-1}$</span>; (v2) at (<span>45\*3.5:2</span>) ; at (<span>45\*3.5:2</span>) <span>$v_{2t^2}$</span>; (v3) at (<span>45\*2.5:2</span>) ; at (<span>45\*2.5:2</span>) <span>$v_1$</span>; (v4) at (<span>45\*1.5:2</span>) ; at (<span>45\*1.5:2</span>) <span>$v_2$</span>; (v5) at (<span>45\*0.5:2</span>) ; (v6) at (<span>45\*-0.5:2</span>) ; (v1)–(v2)–(v3)–(v4)–(v5)–(v6); (v)–(v1); (v)–(v2); (v)–(v3); (v)–(v4); (v)–(v5); (v)–(v6); (v6) \[dotted, very thick, bend left\] to (v1); (u1) at (2.5,0) ; at (2.5,0) <span>$u_{2t^2+2}$</span>; (u2) at (4.5,0) ; at (4.5,0) <span>$u_{2t^2+3}$</span>; (u3) at (8.5,0) ; at (8.5,0) <span>$u_{4t^2+k}$</span>; (u4) at (10.5,0) ; at (10.5,0) <span>$u_{4t^2+1+k}$</span>; (v)–(u1)–(u2); (u2)–(u3); (u3)–(u4);

Graph classes with $prc(G) = rc(G)$
===================================

Let $C_n$ by a cycle of order $n \geq 4.$ Then $$prc(G) = rc(G) = \lceil\frac{n}{2}\rceil.$$

Next observe that any colouring, which makes a tree rainbow connected, is a proper colouring. So we deduce that

Let $T$ by a tree of order $n \geq 2.$ Then $$prc(G) = rc(G) = n-1.$$

Starting with a given tree $T$ we can generate a large variety of classes of graphs satisfying $prc(G)=rc(G).$ For example we can attach to each leaf of $T$ a finite number of cycles each of length at least 4.

Another class of graphs is described in @JLLM2019. Here $g(G)$ denotes the girth of $G.$

Let $G$ be a connected graph with $rc(G) < g(G)-2.$ Then $$prc(G) = rc(G).$$

Graph classes with $prc(G) = \chi'(G)$
======================================

The proper rainbow connection numbers of complete graphs $K_n$ are determined in Theorem \[Thm\_Bau\_Compl\]. Now we consider the proper rainbow connection number of connected graphs whose diameter is $2$.

\[Propo\_diam\] Let $G$ be a connected graph of order $n \geq 3.$ If $diam(G)=2$, then $prc(G)=\chi'(G)$.

Let $c:1\rightarrow[\chi'(G)]$ be a proper edge-colouring of $G.$ Now we show that for every pair ofvertices $u,v\in V(G)$, there is at least one rainbow path. If $uv\in E(G)$, then $uv$ is the rainbow path between the two vertices $u,v$. On the other hand, if $uv\notin E(G)$, there is at least one vertex, say $w$, such that $w\in N_G(u)$ and $w\in N_G(v),$ since $diam(G)=2$. Clearly, $c(uw)\neq c(wv)$, since $G$ is proper. Hence, $uwv$ is the rainbow path connecting two vertices $u,v$. We conclude that $G$ is properly rainbow connected. Thus, $prc(G)\leq\chi'(G)$.

With the aid of Proposition \[Prop\_Lower\_Bau\], we are now able to obtain that $prc(G)=\chi'(G)$.

By using Proposition \[Propo\_diam\], we determine proper rainbow connection numbers of some graphs whose diameter equals $2$.

First, we determine the proper rainbow connection number for wheels.

\[Propo\_wheel\] For each integer $n\geq4$, $prc(W_n)=n$

Suppose that a wheel $W_n$ of order $n+1$ consists of a cycle $C_{n}=v_1v_2\ldots v_nv_1$ and a single vertex $w$ joined to all vertices of cycle $C_n$.

We assign colours $c:E(W_n)\rightarrow[n]$ to all the edges of the wheel $W_n$ as follows: $c(wv_i)=i$, $c(v_iv_{i+1})=i \mod(n)+2$ for $\forall i\in[n-2]$, $c(v_{n-1}v_n)=1$, $c(v_nv_1)=2$. It can be readily seen that $W_n$ is properly coloured. Hence, $\chi'(W_n)\leq n$. On the other hand, $\chi'(W_n)\geq\Delta(W_n)=n$. We deduce that $\chi'(W_n)=n$.

Clearly, $diam(W_n)=2$. By using Proposition \[Propo\_diam\], $prc(W_n)=\chi'(n)=n$. We obtain the result.

Next we determine the proper rainbow connection number for the complete bipartite graph $K_{s,t}.$

\[Thm\_Bipartite\] Let $s,t$ be two integers. If $K_{s,t}$ is a complete bipartite graph, then $prc(K_{s,t})=\max\lbrace s,t\rbrace$.

Let us mention the following result which is very useful to prove our Theorem \[Thm\_Bipartite\].

\[König et al. @Konig1916\] \[Thm\_Konig\_Chi\_Bipar\] If $G$ is bipartite, then $G$ is in Class 1.

Now we are able to prove Thereom \[Thm\_Bipartite\].

With the aid of Theorem \[Thm\_Konig\_Chi\_Bipar\], it can be readily seen that $\chi'(K_{s,t})=\Delta(K_{s,t})=\max\lbrace s,t\rbrace$. On the other hand, $diam(K_{s,t})=2$. By using Proposition \[Propo\_diam\], $prc(K_{s,t})=\chi'(K_{s,t})$.

We conclude that $prc(K_{s,t})=\max\lbrace s,t\rbrace$.

We know that, the chromatic index $\chi'(G)$ depends on the property of $G$ being overfull or not overfull. $G$ is called *overfull* if the number of vertices $n$ is odd, and the number of edges $m$ is greater than $\frac{1}{2}\bigtriangleup(G)(n-1)$. Let us mention Hoffman's result et al. @Hoffman92 on the chromatic index of complete multipartite graph.

\[Hoffman et al. @Hoffman92\] \[Lem\_Hoffman\_complete\_multi\] Let $G$ be a complete multipartite graph. Then $\chi'(G)=\bigtriangleup(G)$ if $G$ is not overfull. Otherwise, $\chi'(G)=\bigtriangleup(G)+1$.

Now the, proper connection number of a complete multipartite graph is determined as follows.

\[Propo\_Multipartite\] Let $G$ be a complete multipartite graph. If $G$ is overfull, then $prc(G)=\bigtriangleup(G)+1$. Otherwise, $prc(G)=\bigtriangleup(G)$.

Suppose that $G$ is a complete multipartite graph. It can be readily seen that $diam(G)=2$. By using Proposition \[Propo\_diam\], $prc(G)=\chi'(G)$.

Now, applying Lemma \[Lem\_Hoffman\_complete\_multi\], $\chi'(G)=\bigtriangleup(G)+1$ if $G$ is overfull or $\chi'(G)=\bigtriangleup(G)$ if $G$ is not overfull. Hence, the result is obtained.

In @Chartrand2008, Chartrand et al. showed that $rc(G)=1$ if and only if $G$ is complete. After that, Caro et al. @Caro2008 investigated graphs with small rainbow connection numbers and they gave a sufficient condition that guarantees $rc(G)=2$.

\[Caro et al. @Caro2008\] Let $G$ be a nontrivial, connected graph of minimum degree $\delta(G)$. If $\delta(G)\geq\frac{n}{2}+log_2n$, then $rc(G)=2$

Next, we show that dense graphs have large proper rainbow connection number.

\[Propo\_minimum\] Let $G$ be a proper edge-coloured graph of order $n$ and minimum degree $\delta(G)$. If $\delta(G)\geq\frac{n-1}{2}$, then $prc(G)= \chi'(G).$

We show that $diam(G) \leq 2.$ Let $u,v \in V(G)$ be two non adjacent vertices. Then $d(u) + d(v) = |N(u) \cup N(V| + |N(u) \cap N(v)| \geq 2 \cdot \frac{n-1}{2} = n-1.$ Since $|N(u) \cup N(v)| \leq n-2,$ we conclude $|N(u) \cap N(v)| \geq 1.$ Hence there is a proper coloured path $uwv$ for a vertex $w \in N(u) \cap N(v).$ This shows that $diam(G) \leq 2.$ Now $prc(G) = \chi'(G)$ follows by Proposition \[Propo\_diam\].

This proof immediately leads to the following extension.

\[Propo\_minimumdegreesum1\] Let $G$ be a proper edge-coloured graph of order $n \geq 3.$ If $d(u) + d(v) \geq n-1$ for every pair of non adjacent vertices $u,v \in V(G),$ then $prc(G)= \chi'(G).$

\[Propo2\_minimum\] Let $G$ be a proper edge-coloured graph of order $n \geq 9$ and minimum degree $\delta(G)$. If $\delta(G)\geq\frac{n-2}{2}$, then $prc(G)= \chi'(G).$

Let $u,w \in V(G)$ be any two vertices. If $d(u,w)\leq 2,$ then $u$ and $w$ are connected by a rainbow path of length at most two. Hence we may assume that $d(u,w) \geq 3.$ Then $N[u] \cup N[w] = V(G)$ implying $\delta(G) = \frac{n-2}{2}.$ Since $G$ is connected we conclude that $d(u,w)=3.$ We may assume $4 \leq d(u) \leq d(w),$ since $n \geq 9.$ Let $U = N(u) = \{u_1, u_2, \ldots, u_{d(u)}\}$ and $W = N(w) = \{w_1, w_2, \ldots, w_{d(w)}\}.$ Suppose $u_iw_j, u_iw_k \in E(G).$ Then at least one of the two paths $uu_iw_jw$ and $uu_iw_kw$ is a rainbow $uw$-path. By symmetry we conclude that $E(U,W)$ is an induced matching. Suppose $u_1w_1 \in E(G),$ but $uu_1w_1w$ is no rainbow $uw$-path. We may assume that $c(uu_1)=c(w_1w)=1, c(u_1w_1)=2.$ Since $N(u_1) \cap W = \{w_1\},$ we conclude that $|N(u_1) \cap (U \setminus \{u_1\})| \geq \delta(G)-2 \geq \frac{n-6}{2} \geq 2.$ We may assume that $u_1u_2,u_1u_3 \in E(G).$ Now $uu_2u_1w_1w$ or $uu_3u_1w_1w$ is a rainbow $uw$-path. Hence $G$ is rainbow connected. Now $prc(G) = \chi'(G)$ follows by Proposition \[Propo\_diam\].

<span>**Sharpness:**</span> For $n=8$ consider the following graph $F_8$ with vertices $V(F_8)=\{u,u_1,u_2,u_3,w,w_1,w_2,w_3\}$ and edges $E(F_8)=\{uu_1,uu_2,uu_3,u_1u_2,u_2u_3,u_1w_1,u_3w_3,$ $w_1w_2,w_2w_3,ww_1,ww_2,ww_3\}.$ Then $\chi'(F_8)=3$ and we may assume that $c(uu_i)=i$ for $1 \leq i \leq 3.$ Then the colours of five further edges are uniquely determined as follows: $c(u_1u_2)=3, c(u_2u_3)=1, c(u_1w_1)=c(u_3w_3)=c(ww_2)=2.$ For the four remaining edges we obtain (1) $c(w_2w_3)=c(ww_1)=3$ and $c(w_1w_2)=c(ww_3)=1$ or (2) $c(w_2w_3)=c(ww_1)=1$ and $c(w_1w_2)=c(ww_3)=3.$

This is a proper edge-colouring of $F_8,$ but $F_8$ is not rainbow connected. If we recolour in (1) the edges $u_2u_3$ and $w_2w_3$ by colour $4,$ then $F_8$ becomes proper rainbow connected. Hence $prc(F_8)=4.$ If we switch in (1) the colours of $u_1u_2, u_2u_3$ and $w_1w_2, w_2w_3,$ then $F_8$ becomes rainbow connected showing that $rc(F_8)=3 = diam(F_8)$.

\(u) at (0,0); at (0,0) <span>$u$</span>; (u1) at (2,1); at (2,1) <span>$u_1$</span>; (u2) at (2,0); at (2,0) <span>$u_2$</span>; (u3) at (2,-1); at (2,-1)<span>$u_3$</span>; (w1) at (4,1); at (4,1) <span>$w_1$</span>; (w2) at (4,0); at (4,0) <span>$w_2$</span>; (w3) at (4,-1); at (4,-1) <span>$w_3$</span>; (w) at (6,0); at (6,0) <span>$w$</span>; (u)–(u1)–(w1); (u)–(u2); (u)–(u3)–(w3); (u1)–(u2)–(u3); (w)–(w1); (w)–(w2); (w)–(w3); (w1)–(w2)–(w3);

This proof immediately leads to the following extension.

\[Propo\_minimumdegreesum2\] Let $G$ be a proper edge-coloured graph of order $n \geq 9.$ If $d(u) + d(v) \geq n-2$ for every pair of non adjacent vertices $u,v \in V(G),$ then $prc(G)= \chi'(G).$

\[Propo3\_minimum\] Let $G$ be a proper edge-coloured graph of order $n \geq 9$ and minimum degree $\delta(G)$. If $\delta(G)\geq\frac{n+k}{3}$ for an integer $k \geq 3$, then $prc(G)= \chi'(G).$

Let $u,w \in V(G)$ be any two vertices. If $d(u,w)\leq 2,$ then $u$ and $w$ are connected by a rainbow path of length at most two. Hence we may assume that $d(u,w) \geq 3.$\
<span>**Case 1**</span> $d(u,w)=3$\
Let $R = V(G) \setminus (N[u] \cup N[w]).$ Then $|R| \leq n - 2(\delta + 1).$ Following arguments in the previous proof we conclude that $E(U,W)$ is an induced matching. Then $\delta \leq d(u_1) \leq |R|+4 \leq n - 2\delta +2$ implying $\delta \leq \frac{n}{3},$ a contradiction.\
<span>**Case 2**</span> $d(u,w)=4$\
Let $uu_1xw_1w$ be a $uw$-path of length $4,$ and let $R = V(G) \setminus (N[u] \cup N[w]).$ Thus $x \in R$ and $|R| \leq n - 2(\delta +1).$ If $|N(x) \cap (U \cup W)| \geq 5,$ then there is always a rainbow $uw$-path $uu_ixw_jw$ for two vertices $u_i$ and $w_j.$ Hence we may assume that $|N(x) \cap (U \cup W)| \leq 4$ implying $\delta - 4 \leq d(x)-4 \leq |R|-1 \leq n - 2\delta -3.$ This gives $\delta \leq \frac{n+1}{3},$ a contradiction.\
<span>**Case 3**</span> $d(u,w)=5$\
Let $uu_1x_1x_2w_1w$ be a $uw$-path of length $5,$ and let $R = V(G) \setminus (N[u] \cup N[w]).$ Thus $x_1,x_2 \in R$ and $|R| \leq n - 2(\delta +1).$ Note that $N(x_1) \cap W = N(x_2) \cap U = \emptyset.$ If $|N(x_1) \cap U| \leq 5,$ then $\delta - 5 \leq d(x)-5 \leq |R|-1 \leq n - 2\delta -3.$ This gives $\delta \leq \frac{n+2}{3},$ a contradiction. Hence we may assume that $|N(x_1) \cap U \geq 6.$ Now there is always a rainbow $uw$-path $uu_ix_1x_2w_1w$ for a vertex $u_i.$\
<span>**Case 4**</span> $d(u,w)=t \geq 6$\
Let $uu_1x_1x_2 \ldots x_{t-3}w_1w$ be a $uw$-path of length $t.$ Then $N[x_2] \cap N[u] = N[x_2] \cap N[w] = \emptyset$ implying $3(\delta +1) \leq n,$ a contradiction.

Lower bound
===========

In this section, we consider the lower bound of proper rainbow connection in dense graphs and some conditions on size of graphs.

Dense graphs
------------

Dense graphs tend to have a small rainbow connection number. However, dense graphs have a large proper rainbow connection number. This follows immediately from its average degree.

\[Propo\_average\_degree\] Let $G$ be a nontrivial, connected graph of order $n\geq2$ and average degree $\overline{d}(G)=\frac{2\vert E(G)\vert}{n}$. Then $prc(G)\geq\lceil\overline{d}(G)\rceil$.

It can be readily seen that $prc(G)\geq\bigtriangleup(G)$ since $prc(G)\geq\chi'(G)$ by Proposition \[Prop\_Lower\_Bau\] and $\chi'(G)\geq\bigtriangleup(G)$ by Vizing's Theorem. On the other hand, $\bigtriangleup(G)\geq\lceil\overline{d}(G)\rceil$. Hence, $prc(G)\geq\lceil\overline{d}(G)\rceil$.

We obtain the result.

\[Propo1\_size\_graph\] Let $G$ be a connected graph of order $n$ and size $\vert E(G)\vert\geq k\frac{n}{2}$. Then $prc(G)\geq k.$

By the handshaking lemma we obtain $\frac{2\vert E(G)\vert}{n}=\overline{d}(G)\geq k$. Now the result follows by Proposition \[Propo\_average\_degree\].

Size of graphs
--------------

The problem of rainbow connection depending on size of graphs are studied by Kemnitz and Schiermeyer in @Kemnitz2011 as follows: For every integer $k$ with $1\leq k\leq n-1$, compute and minimize the function $f(n,k)$ with the following property: If $\vert E(G)\vert\geq f(n,k)$, then $rc(G)\leq k$, where $$f(n,k)\geq {{n-k+1}\choose 2}+(k-1).$$ It has been shown in @Kemnitz2011 [@LLS; @KPSW] that equality holds for $k=1,2,3,4,n-6,n-5,n-4,n-3,n-2,n-1.$ Now, we obtain the following result.

\[theorem\_size\_graph\] Let $G$ be a connected proper edge-coloured graph of order $n \geq 3.$ If $$|E(G)| \geq {n-2 \choose 2} + 2,$$ then $prc(G)= \chi'(G)$ or $G \in \{P_4, Z_2, G_{6.3}\}.$

Let $G$ be a connected graph of order $n \geq 3$ and size $|E(G)| \geq {n-2 \choose 2} + 2.$ Then $\Delta(G) \geq \lceil\overline{d}(G)\rceil \geq \lceil n-5+\frac{10}{n}\rceil \geq n-4.$

Let $w \in V(G)$ be a vertex with $d(w) = \Delta(G),$ and let $N(w) = W = \{w_1, w_2, \ldots, w_{\Delta(G)}\}$ be its neighours. We distinguish four cases.

1.  If $\Delta(G)=n-1,$ then $G[\{ww_i | 1 \leq i \leq n-1\}]$ induces a spanning subgraph $H$ of $G,$ which is rainbow-connected. Hence $G$ is rainbow-connected.

2.  If $\Delta(G) = n-2,$ then let $V(G) \setminus N[w] = \{u\}.$ First observe that $N(u) \subset N(w).$ So we may assume that $uw_i \in E(G)$ for $1 \leq i \leq d(u).$ If $d(u) \geq 2,$ then $G[\{ww_i | 1 \leq i \leq n-2\} \cup \{uw_1, uw_2\}]$ induces a spanning subgraph $H$ of $G,$ which is rainbow-connected. Hence $G$ is rainbow-connected. If $d(u)=1,$ let $c(w_1u)=1, c(ww_1)=2.$ If $c(ww_i) \neq 1$ for $2 \leq i \leq n-2,$ then $G$ is rainbow-connected. Hence we may assume that $c(ww_2)=1.$ Then we are sure that all pairs of vertices $x,y \in V(G)$ are rainbow-connected except for the pair $(u, w_2),$ if $d(u,w_2) \geq 3.$ Hence we may assume that $w_1w_2 \notin E(G).$ Suppose there is a vertex $w_i \in N(w_1) \cap N(w_2)$ for some $3 \leq i \leq n-2.$ We may assume that $c(w_1w_i)=3.$ Then $c(w_2w_i) \neq 1,3$ and so $uw_1w_iw_2$ is a rainbow path. Suppose there is no such vertex $w_i.$ Then $|E(\overline{G})| \geq 1 + (n-3) + 1 + (n-4) = 2n-5,$ which implies that $|E(G)| = {n-2 \choose 2} +2.$ Thus we have $d(u)=1$ and $d(w_1)+d(w_2)=3+(n-4)=n-1.$ Therefore, $G-\{w_1,w_2,u\} \cong K_{n-3}.$ We may further assume that $w_2w_i \in E(G)$ for $3 \leq i \leq d(w_2)+1.$

    Suppose first that $d(w_2) \geq 3.$ If $c(w_2w_3)=2,$ then $uw_1ww_4w_2$ is a rainbow $uw_2$-path. If $c(w_2w_3) \neq 2,$ then $uw_1ww_3w_2$ is a rainbow $uw_2$-path. Suppose next that $d(w_2)=2,$ which implies $n \geq 5.$ If $c(w_2w_3) \neq 2,$ then $uw_1ww_3w_2$ is a rainbow $uw_2$-path. Hence we may assume that $c(w_2w_3)=2.$ Then $uw_1w_4w_3w_2$ is a rainbow $uw_2$-path for $n \geq 6.$ If $n=5,$ then $G \cong Z_2.$ Note that $\chi'(Z_2)=rc(Z_2=3,$ but $prc(Z_2)=4.$ Hence $Z_2$ is an exceptional graph.

    Finally suppose that $d(w_2)=1.$ Then $G$ consists of a complete graph of order $n-2$ induced by $V(G) \setminus \{u,w_2\}$ and two pendant edges attached at $w$ and $w_1.$ If $n \geq 4$ is odd, then $\chi'(G)=n-2=\Delta(G).$ Observe that the $K_{n-2}$ is coloured with $n-2$ colours and that $w$ and $w_1$ have distinct palettes of colours for their incident edges. Hence the pendant edges $ww_2$ and $w_1u$ have distinct colours. This shows that $G$ is rainbow connected. If $n \geq 4$ is even, then $G \cong P_4$ for $n = 4$ implying $prc(G)=rc(G)=3.$ Therefore, $P_4$ is an exceptional graph, since $\chi'(P_4)=2.$

    If $n \geq 6,$ take an optimal edge colouring of the $K_{n-2}$ using $n-3$ colours. Now switch the colour from $ww_3$ to the edge $ww_2,$ and colour the edges $ww_3$ and $w_1u$ with a new colour. Now observe that this colouring makes $G$ properly rainbow connected.\

    (u1) at (0,0); (u2) at (-1,-1); (u3) at (1,-1); (u4) at (0,1); (u5) at (0,2); (u1)–(u2)–(u3)–(u1); (u1)–(u4)–(u5);

3.  If $\Delta(G) = n-3,$ then let $V(G) \setminus N[w] = U = \{u_1,u_2\}.$ We first distinguish two cases.

    <span>**Case 1**</span> $u_1u_2 \in E(G)$\
    We first show that $G - w_i$ is connected for $1 \leq i \leq n-3.$ Suppose that $G - w_i$ is disconnected for some $i$ with $1 \leq i \leq n-3.$ Then $|E(G)| \leq |E(G[N[w]-w_i])|+|E(G[\{u_1,u_2\}])|+d(w_i) \leq {n-3 \choose 2} + 1 + (n-3) < {n-2 \choose 2} + 2,$ a contradiction. Now $G-w_1$ and $G-w_2$ both have size at least ${n-2 \choose 2} + 2 - (n-3) = {(n-1)-2 \choose 2} + 2.$ So by induction both $G-w_1$ and $G-w_2$ are rainbow connected or an exceptional graph. Furthermore $w_1$ and $w_2$ are rainbow connected, since $1 \leq d(w_1,w_2) \leq 2.$ This shows that $G$ is rainbow connected or an exceptional graph.

    <span>**Case 2**</span> $u_1u_2 \notin E(G)$\
    Let $d(u_1) \geq d(u_2) \geq 1.$ Then $d(w) + \sum_{i=1}^{n-3}d(w_i) \leq (n-3) + (n-3)(n-3) - d(u_1)-d(u_2)$ implying $|E(G)| \leq {n-2 \choose 2} + \frac{d(u_1)+d(u_2)}{2} < {n-2 \choose 2} + 2$ for $d(u_1)+d(u_2) \leq 3,$ a contradiction. Hence we may assume that $d(u_1) + d(u_2) \geq 4.$ Now if $d(u_1) \geq 3, d(u_2)=1$ or $d(u_1) \geq 2, d(u_2) \geq 2,$ then there are always two vertices $w_i, w_j$ such that $G - w_i$ and $G - w_j$ are both connected. This shows that $G$ is rainbow connected or an exceptional graph.

    This discussion shows, that in both cases $G$ is either properly rainbow connected or an exceptional graph. So suppose that $m(G - w_i) = {n-3 \choose 2} + 2$ and $G - w_i$ is not properly rainbow connected for some $1 \leq i \leq d(w).$ We may choose the labeling of the vertices of $G$ such that $G - w_1$ is not properly rainbow connected.

    If $n=5,$ then $G - w_1 \cong P_4.$ Taking into account that $d(w_1)=2=\Delta(G)$ we conclude that $G \cong C_5.$ Now we have $prc(C_5)=3=rc(C_5)=\chi'(C_5).$

    If $n=6,$ then $G - w_1 \cong Z_2.$ Now up to isomorphism the following three graphs $G_{6.1},G_{6.2}$ and $G_{6.3}$ are possible.

    1.  $G_{6.1}: c(ww_2)=c(w_1w_3)=c(u_1u_2)=1, c(ww_1)=c(w_2w_3)=2, c(ww_3)=c(w_1u_1)=c(w_2u_2)=3.$\
        This shows that $prc(G_{6.1})=rc(G_{6.1})=\chi'(G_{6.1})=3.$

    2.  $G_{6.2}: c(ww_2)=c(w_1w_3)=c(u_1u_2)=1, c(ww_1)=c(w_2w_3)=2, c(ww_3)=c(w_1u_1)=3, c(w_2u_1)=4.$\
        Observe that $\chi'(G_{6.2})=4.$ This shows that $prc(G_{6.2})=\chi'(G_{6.2})=4,$ whereas $rc(G_{6.2})=3.$

    3.  For $G_{6.3}$ we can show that $rc(G_{6.3})=\chi'(G_{6.3})=3,$ whereas $prc(G_{6.3})=4.$ Up to a permutation of the colours $G_{6.3}$ has to be coloured as follows: $G_{6.3}: c(ww_1)=c(w_2w_3)=c(u_1u_2)=1, c(ww_2)=c(w_1u_2)=2, c(ww_3)=c(w_2u_2)=c(w_1u_1)=3.$ Thus $G_{6.3}$ is an exceptional graph.

    If $n=7,$ then $G - w_1 \cong G_{6.3}.$ Observe that $d(w_1)=4.$ Now we can always find two vertices $x,y \in V(G_{6.3})$ such that $d(x,y) \leq 2,$ $G - x$ and $G - y$ are connected, and $\Delta(G-x)=\Delta(G-y)=4.$ Hence, $G$ is no exceptional graph. No by induction it follows that there are no exceptional graphs $G$ with size ${n-2 \choose 2} + 2$ for all $n \geq 7.$

    <span>0.28</span>

    (w3) at (0,0); at (0,0) <span>$w_3$</span>; (w1) at (-1.5,0); at (-1.5,0) <span>$w_1$</span>; (w2) at (1.5,0); at (1.5,0) <span>$w_2$</span>; (w) at (0,1.5); at (0,1.5) <span>$w$</span>; (u1) at (-0.75,-1.5) ; at (-0.75,-1.5) <span>$u_1$</span>; (u2) at (0.75,-1.5) ; at (0.75,-1.5) <span>$u_2$</span>; (w1)–(w)–(w2)–(u2)–(u1)–(w1)–(w3)–(w2); (w3)–(w); at (0,-1.5) <span>$1$</span>; at (-1,-0.75) <span>$3$</span>; at (1,-0.75) <span>$3$</span>; at (-0.75,0) <span>$1$</span>; at (0.75,0) <span>$2$</span>; at (-0.75,0.5) <span>$2$</span>; at (0.75,0.5) <span>$1$</span>; at (0,0.75) <span>$3$</span>;

    <span>0.4</span>

    (w3) at (0,0); at (0,0) <span>$w_3$</span>; (w1) at (-1.5,0); at (-1.5,0) <span>$w_1$</span>; (w2) at (1.5,0); at (1.5,0) <span>$w_2$</span>; (w) at (0,1.5); at (0,1.5) <span>$w$</span>; (u1) at (-0.75,-1.5) ; at (-0.75,-1.5) <span>$u_1$</span>; (u2) at (0.75,-1.5) ; at (0.75,-1.5) <span>$u_2$</span>; (w1)–(w)–(w2)–(u1)–(w1)–(w3)–(w2); (w3)–(w); (u1)–(u2); at (0,-1.5) <span>$1$</span>; at (-1.1,-0.55) <span>$3$</span>; at (-0.75,0) <span>$1$</span>; at (0.75,0) <span>$2$</span>; at (-0.75,0.5) <span>$2$</span>; at (0.75,0.5) <span>$1$</span>; at (0,0.75) <span>$3$</span>; at (0.85,-0.55) <span>$4$</span>;

    <span>0.28</span>

    (w2) at (0,0); at (0,0) <span>$w_2$</span>; (w1) at (-1.5,0); at (-1.5,0) <span>$w_1$</span>; (w3) at (1.5,0); at (1.5,0) <span>$w_3$</span>; (w) at (0,1.5); at (0,1.5) <span>$w$</span>; (u1) at (-0.75,-1.5) ; at (-0.75,-1.5) <span>$u_1$</span>; (u2) at (0.75,-1.5) ; at (0.75,-1.5) <span>$u_2$</span>; (w1)–(w)–(w3)–(w2)–(u2)–(u1)–(w1); (w1)–(u2); (w)–(w2); at (0,-1.5) <span>$1$</span>; at (-1.1,-0.55) <span>$3$</span>; at (0.75,0) <span>$1$</span>; at (-0.75,0.5) <span>$1$</span>; at (0.75,0.5) <span>$3$</span>; at (0,0.75) <span>$2$</span>; at (0.85,-0.55) <span>$3$</span>; at (0,-0.55) <span>$2$</span>;

4.  If $\Delta(G) = n-4,$ then $n \geq 7.$ Let $V(G) \setminus N[w] = U = \{u_1,u_2,u_3\}.$ We distinguish three cases.

    <span>**Case 1**</span> $U$ is connected\
    We first show that $G - w_i$ is connected for $1 \leq i \leq n-4.$ Suppose that $G - w_i$ is disconnected for some $i$ with $1 \leq i \leq n-4.$ Then $|E(G)| \leq |E(G[N[w]-w_i])|+|E(G[\{u_1,u_2,u_3\}])|+d(w_i) \leq {n-4 \choose 2} + 3 + (n-4)
    = {n-3 \choose 2} + 3 < {n-2 \choose 2} + 2,$ a contradiction. Hence we may assume that $|N(U) \cap W| \geq 2.$

    <span>**Fact 1:**</span> Then there are always two vertices $w_i, w_j$ such that $G - w_i$ and $G - w_j$ are both connected. Now $G-w_i$ and $G-w_j$ both have size at least ${n-2 \choose 2} + 3 - (n-4) = {(n-1)-2 \choose 2} + 4.$ So by induction both $G-w_i$ and $G-w_j$ are rainbow connected. Furthermore $w_1$ and $w_2$ are rainbow connected, since $1 \leq d(w_1,w_2) \leq 2.$ This shows that $G$ is rainbow connected.

    <span>**Case 2**</span> $|E(U)|=1$\
    We may assume that $E(U)=u_1u_2.$ If $|E(U,W)| \leq 3,$ then $\sum_{v \in V(G)}d(v) \leq (n-3)(n-4)+2+3$ implying $m(G) \leq {n-3 \choose 2} + 2 < {n-2 \choose 2} + 2,$ a contradiction. Hence we may assume that $|E(U,W)| \geq 4.$ Now considering the two components $\{u_1, u_2\}$ and $u_3$ of $U$ as two vertices we can follow the previous Case 2 for $\Delta(G)=n-3.$

    <span>**Case 3**</span> $E(U)= \emptyset$\
    Let $d(u_1) \geq d(u_2) \geq d(u_3) \geq 1.$ If $d(u_3) \geq 2,$ then there are always two vertices $w_i, w_j$ such that $G - w_i$ and $G - w_j$ are connected. Moreover, $d(w_i, w_j) \leq 2$ and we apply Fact 1. So we may assume that $d(u_3)=1.$ Let $u_3w_1 \in E(G).$ If $|E(\{u_1, u_2\},W-w_1| \geq 4,$ then there are two vertices $w_i, w_j, 2 \leq i < j \leq j$ such that $G- w_i$ and $G - w_j$ are connected and we apply Fact 1. Hence we may assume that $|E(U,W)| \leq 3 + 3 = 6.$ This implies $|E(G)| \leq {n-3 \choose 2} + 6 < {n-2 \choose 2} + 2,$ a contradiction.

(v1) at (0,0) ; at (0,0) <span>$v_1$</span>; (v2) at (-1,-1) ; at (-1,-1) <span>$v_2$</span>; (v3) at (-0.5,-2) ; at (-0.5,-2) <span>$v_3$</span>; (v4) at (1.5,-2) ; at (1.5,-2) <span>$v_{n-4}$</span>; (v5) at (2,-1) ; at (2,-1) <span>$v_{n-3}$</span>; (v6) at (1,0) ; at (1,0) <span>$v_{n-2}$</span>; (v1)–(v2)–(v3); (v4)–(v5)–(v6); (v1)–(v3); (v1)–(v4); (v1)–(v5); (v2)–(v4); (v2)–(v5); (v2)–(v6); (v3)–(v4); (v3)–(v5); (v3)–(v6); (v4)–(v5); (v4)–(v6); (v5)–(v6); (v4) \[dotted, very thick, bend left\] to (v3); (v7) at (0,1) ; at (0,1) <span>$v_{n-1}$</span>; (v8) at (1,1) ; at (1,1) <span>$v_n$</span>; (v1)–(v7); (v6)–(v8);

<span>**Sharpness:**</span> For even $n \geq 6$ take a complete graph of order $n-2$ and label its vertices $v_1, v_2, \ldots, v_{n-2}.$ Now we add two vertices $v_{n-1}, v_n,$ add the edges $v_1v_{n-1},v_{n-2}v_n,$ and delete the edge $v_1v_{n-2}.$ Let $F_n$ denote the resulting graph. Then $|E(F_n)|= {n-2 \choose 2}+1, \Delta(F_n)=\chi'(F_n)=n-3, rc(F_n)=diam(F_n)=4,$ but $prc(G)=n-2,$ if $n$ is even. This can be seen as follows. In any edge colouring of $F_n$ using $n-3$ colours, $F_n - \{v_{n-2}, v_{n-1}, v_n\}$ uses all $n-3$ colours, each on $\frac{n-4}{2}$ edges. Applying the same argument on $F_n - \{v_1, v_{n-1}, v_n\},$ we deduce that $v_1$ and $v_{n-2}$ have the same palette of $n-4$ colours for their incident edges in $F_n - \{v_{n-1},v_n\}.$ Suppose these colours are $1, 2, \ldots, n-4.$ Then both edges $v_1v_{n-1}$ and $v_{n-2}v_n$ obtain colour $n-3.$ But then there is no rainbow $v_{n-1}v_n$-path.

<span>1</span>

{'source': 'arXiv_out/1911'}