2-swappable graphs

Peer review under responsibility of Kalasalingam University.

Abstract

Let $G=(V,E)$ be a graph, by $\left(\genfrac{}{}{0ex}{}{V}{2}\right)$, we mean the set of all 2-combinations of $V$. We say that a graph $G$ is $k$-swappable if for every edge $e\in E$, there are two sets $A\subset E$, $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$ such that $e\in A$, $\left|A\right|\le k$, and $G\cong (V,(E\setminus A)\cup B)$. The swapping number of $G$ is the minimum $k>0$ such that $G$ is $k$-swappable.

Let $d\ge 2$ be an integer. Every tree with exactly one vertex of degree $d$ and remaining vertices of degree $d+1$ or 1 we will call a $d$-nary tree.

In this paper we give sufficient conditions for general graphs as well as sufficient and necessary conditions for a $d$-nary tree for $d>2$ to be 2-swappable.

Keywords:

• Swapping number
• $k$-swappable
• Near automorphism
• Edge reconstruction
• Graph automorphism

1 Introduction

In this paper, we deal with finite, simple and undirected graphs. Let us consider a graph $G=(V,E)$, whose number of vertices we call the order and number of edges we call the size of $G$. If $S\subset V$, then we will understand $G-S$ to mean the graph induced by $G$ on the vertex set $V\setminus S$. By $\left(\genfrac{}{}{0ex}{}{V}{2}\right)$, we mean the set of all 2-combinations of $V$. A vertex $x\in V$ is called primary if $deg\left(x\right)\ge 3(de{g}_G\left(x\right)\ge 3)$. A $leaf$ is a vertex of degree one.

The girth of a graph $G$ is the length of a shortest cycle contained in the graph and it is denoted by $\mathrm{girth}\left(G\right)$. If the graph does not contain any cycles its girth is defined to be infinity.

A spider is a tree $T$ in which exactly one vertex $x$ has degree greater than 2. We call $x$ the central vertex of $T$. An arm of a spider $T$ is a connected component of $T\setminus \left\{x\right\}$. We denote a spider with central vertex of degree $d$ by $\mathfrak{S}(a_1,a_2,\dots ,a_d)$, where $a_1,a_2,\dots ,a_d$ are the numbers of vertices in the arms; thus $\left|V\left(\mathfrak{S}(a_1,a_2,\dots ,a_d)\right)\right|=1+a_1+a_2+\cdots +a_d$.

Let $d\ge 2$ be an integer. Every tree with exactly one vertex of degree $d$ and remaining vertices of degree $d+1$ or 1 we will call a $d$-nary tree. The vertex of degree $d$ we will call the root of a $d$-nary tree and denote by $r$.

In this paper we will consider $k$-swappable graphs. The definition of $k$-swappable was given in [1].

Definition 1

Let $G=(V,E)$ be a graph and let $k$ be a positive integer. We say that $G$ is $k$-swappable if for every edge $e\in E$, there are two sets $A\subset E$, $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$ such that $e\in A$, $\left|A\right|\le k$, and $G\cong (V,(E\setminus A)\cup B)$. The swapping number of $G$ is the minimum $k$ such that $G$ is $k$-swappable.

There is an interesting motivation for investigation of swappable graphs [1]. Consider a network connecting different computing resources; such a network is modelled by a graph. Suppose that the network works if and only if it has an exact structure $G$ (logical topology of the network), so if any of the connections breaks then the network does not work. Suppose that connections between nodes are expensive to add or remove, so we are looking for the minimum number of new connections in a broken network in order to obtain the structure $G$.

In [1] Froncek et al. classified all 1-swappable trees and unicyclic graphs, and proved that the expected value of the swapping number grows linearly with the size of the graph. They proved the following theorem:

Theorem 1

Let $T$ be a tree on two or more vertices. Then $T$ is 1-swappable if and only if $T$ is a path on at least three vertices or $T\cong \mathfrak{S}(2,1,1)$ or $T\cong \mathfrak{S}(3,2,1)$.

Ross found four infinite families of $r\ge 3$ regular graphs that are 2-swappable, [2]. The aim of this article is a characterization of $2$-swappable $d$-nary trees for $d>2$.

2 Some $2$-swappable graphs

In this section we present some family of $2$-swappable graphs.

Theorem 2

Let $G=(V,E)$ be a graph satisfying the following conditions:

1.	$\mathrm{girth}\left(G\right)>4$,

2.	any primary vertices $x,y\in V$ are not neighbours,

3.	for any leaf there exists a leaf with different neighbour,

then $G$ is $2$-swappable graph.

Proof

Let $e=xy\in E$.

Suppose first that $x$ is a leaf. By assumption 3 there exists a leaf $x^{\prime }\in V$ such that $y\notin N\left(x^{\prime }\right)=\left\{y^{\prime }\right\}$. Let $A=\{xy,x^{\prime }{y}^{\prime }\}$ and $B=\{x{y}^{\prime },x^{\prime }y\}$. Notice that $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$ and $G\cong (V,(E\setminus A)\cup B)$.

From now by assumption 2 without loss of generality we can assume that $x$ has degree $2$ and $N\left(x\right)=\{y,z\}$. Let $N\left(z\right)=\{x,z_i,i=1,\dots ,deg\left(z\right)-1\}$ and $N\left(y\right)=\{x,y_i,i=1,\dots ,deg\left(y\right)-1\}$. Let us consider two cases:

Case 1. $deg\left(z\right)=1$

Let $A=\left\{xy\right\}$ and $B=\left\{yz\right\}$. Since $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$, $G\cong (V,(E\setminus A)\cup B)$.

Case 2. $deg\left(z\right)=2$

Let $A=\{xy,z{z}_1\}$ and $B=\{x{z}_1,yz\}$. Since $\mathrm{girth}\left(G\right)>4$, observe that $z_1\ne y$. Notice that $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$ and $G\cong (V,(E\setminus A)\cup B)$.

Case 3. $deg\left(z\right)>2$

If $deg\left(z_1\right)=1$ then $A=\left\{xy\right\}$ and $B=\left\{y{z}_1\right\}$ and hence $G\cong (V,(E\setminus A)\cup B)$.

If $deg\left(z_1\right)\ne 1$ then by assumption 2 $deg\left(z_1\right)=2$ and $N\left(z_1\right)=\{z,t\}$. Note that $t\ne y$, because $\mathrm{girth}\left(G\right)>4$. Let now $A=\{xy,z_{1}t\}$ and $B=\{xt,y{z}_1\}$. It follows that $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$ and $G\cong (V,(E\setminus A)\cup B)$.

Recall that there are $r\ge 3$ regular graphs that are 2-swappable [2]. Therefore the condition 2 given in Theorem 2 is not necessary. Moreover, in Fig. 1 we show that none of the conditions from Theorem 2 is necessary.

Fig. 1 Examples of 2-swappable graphs.

3 The family of $d$-nary trees

Let $T_d=(V,E)$ be a $d$-nary tree with the root $r$ and let $v\in V$. Then there is exactly one path joining vertices $r$ and $v$ in $T_d$. Let $d(r,v)$ denote the distance of vertices $r$ and $v$. We will usually refer to a path by one of the sequences of consecutive vertices. That is, for vertices $v$, $w$ let $(v,w)$-path denote the path from $v$ to $w$.

Let $v^{\prime }\in V$ such that $v^{\prime }v\in E$ and $v^{\prime }$ is a vertex of the $(r,v)$-path. A branch of $T_d$ pointed by the vertex $v$, denoted by $B\left[v\right]$, is a connected component of $T_d\setminus \left\{v^{\prime }\right\}$ with $v$ as a vertex. Observe that $B\left[v\right]$ is a $d$-nary tree or a vertex. Let $u\in V$ such that $v$ is a vertex of $(r,u)$-path. A twig pointed by the vertex $v$ and determined by the vertex $u$, denoted by $T_u\left[v\right]$, is the graph $B\left[v\right]\setminus B\left[v^{\prime \prime }\right]$, where $v^{\prime \prime }\in N\left(v\right)\cap B\left[v\right]$ and $v^{\prime \prime }$ is a vertex of $(r,u)$-path.

Let $(x_1,\dots ,x_i,\dots ,x_k)$ be $(x_1,x_k)$-path and $(y_1,\dots ,y_i,\dots ,y_k)$ be $(y_1,y_k)$-path. If there are vertices $u_x$, $u_y\in V$ such that twigs $T_{u_x}\left[x_i\right]$ and $T_{u_y}\left[y_i\right]$ are isomorphic for $i=1,\dots ,k$, then we say that $(x_1,x_k)$-path and $(y_1,y_k)$-path are twins (or more precisely the paths are twins according to the vertex $u_x$ for $(x_1,x_k)$-path and the vertex $u_y$ for $(y_1,y_k)$-path). We say that $(x_1,x_k)$-path is symmetric (symmetric according to the vertex $u$) if there is a vertex $u\in V$ such that for every $i\in \{1,\dots ,k\}$ twigs $T_u\left[x_i\right]$ and $T_u\left[x_{k+1-i}\right]$ are isomorphic and $k\ge 2$. The $(x_1,x_k)$-path is sequential (according to the vertex $u$) if there are a vertex $u$ and $j\in \{1,\dots ,k-1\}$ such that $j|k$ and twigs $T_u\left[x_i\right]$ and $T_u\left[x_{i+j}\right]$ are isomorphic graphs for $i\in \{1,\dots ,k-j\}$ and $k\ge 3$.

Let $vw\in E$ such that $v$ is a vertex of $(r,w)$-path. We will write that the edge $vw$ is adjacent to a symmetric path if there is at least one of vertices $u$, $u^{\prime }$ such that $(u,v)$-path is symmetric according to $w$ or $(w,u^{\prime })$-path is symmetric, where $u$ is a vertex of $(r,v)$-path, $w$ is a vertex of $(r,u^{\prime })$-path. We say that the edge $vw$ is added to a sequential path if $(r,v)$-path is sequential according to $w$. We say that the edge $vw$ joins twin paths if there are vertices $u$, $u^{\prime }\in V$ which are not vertices of $(r,w)$-path and such that $(r,v)$-path according to $w$ and $(w,u)$-path according to $u^{\prime }$ are twins (see Fig. 2).

Fig. 2 An example of 2-swappable 3-nary tree.

Theorem 3

Let $T_d=(V,E)$, $d\ge 3$ be a $d$-nary tree with the root $r$. The only 2-swappable $T_d\cong K_{1,d}$ $(d\ge 3)$ is $K_{1,3}$. The graph $T_d\ncong K_{1,d}$ is 2-swappable if and only if for every edge $vw\in E$, $deg\left(w\right)>1$, where $v$ is a vertex of $(r,w)$-path, one of the following conditions holds:

(i) $vw$ is adjacent to a symmetric path,

(ii) $vw$ is added to a sequential path,

(iii) $vw$ joins twins paths,

(iv) there is a vertex $w^{\prime }\in V\setminus N\left(v\right)$ such that branches $B\left[w\right]$, $B\left[w^{\prime }\right]$ are isomorphic graphs,

(v) there is a vertex $u\ne v$ such that $(r,v)$-path according to $w$ and $(r,u)$-path are twins

(vi) (only for $d=3$ and $e=rw$) there is a leaf $l\notin B\left[w\right]$ such that $d(r,l)\in \{1,2\}$ or $(u,u^{\prime })$-path is symmetric according to $l$, where $ru$, $u^{\prime }l\in E$.

Proof

Let $T_d=K_{1,3}$. Set $N\left(r\right)=\{v_1,w_1,u_1\}$. Let $e=r{v}_1$. If $A=\{r{v}_1,r{w}_1\}$, $B=\{u_1{v}_1,u_1{w}_1\}$ we obtain that $T_d$ and $(V,(E\setminus A)\cup B)$ are isomorphic. It is easy to see that it is the only 2-swappable star $K_{1,d}$.

We can assume that $T_d\ncong K_{1,d}$.

Let us consider $e=vl\in E$ such that $deg\left(l\right)=1$. Since $T_d\ne K_{1,d}$ there is a leaf $l^{\prime }\in V$ such that $v\notin N\left(l^{\prime }\right)=\left\{v^{\prime }\right\}$. Then $T_d\cong (V,(E\setminus \{vl,v^{\prime }{l}^{\prime }\})\cup \{v{l}^{\prime },v^{\prime }l\})$. Hence such edges have no influence property of 2-swappability. From now we will consider edges not at leaves.

Sufficiency. Let $e=vw\in E$ and let $v$ be a vertex of $(r,w)$-path. In every case we will find sets $A$ and $B$ such that $e\in A\subset E$, $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$, $\left|A\right|\le 2$ and graphs $(V,(E\setminus A)\cup B)$ and $T_d$ are isomorphic.

Let us first suppose that $vw$ is adjacent to a symmetric path. Let us assume that there are vertices $u$, $u^{\prime }\in V$ such that $(w,u)$-path is symmetric according to $u^{\prime }$. We set $A=\{vw,u{u}^{\prime }\}$ and $B=\{vu,w{u}^{\prime }\}$. If $(v,r)$-path is symmetric according to $w$ then $A=\left\{vw\right\}$ and $B=\left\{rw\right\}$. If there is a vertex $u\in V\setminus \left\{r\right\}$ such that $u$ is a vertex of $(r,v)$-path and $(u,v)$-path is symmetric according to $w$ then we set $A=\{vw,u{u}^{\prime }\}$ and $B=\{u^{\prime }v,uv\}$, where $u^{\prime }$ is the only neighbour of $u$ on $(r,u)$-path.

Suppose that $vw$ is added to a sequential path. If $(r,v)$-path is an edge then $A=\left\{vw\right\}$ and $B=\left\{rw\right\}$. Otherwise, there are consecutive vertices $x_j$, $x_{j+1}$, $x_{j+2}$ of $(r,v)$-path such that $T_w\left[r\right]\cong T_w\left[x_{j+1}\right]$, $T_w\left[v\right]\cong T_w\left[x_j\right]$. We set $A=\{vw,x_j{x}_{j+1}\}$, $B=\{x_{j}w,rv\}$.

Assume that $vw$ joins twins paths. Let $u$, $u^{\prime }$ be vertices such that $(r,v)$-path according to $w$ and $(w,u)$-path according to $u^{\prime }$ are twins. Then we set $A=\{vw,u{u}^{\prime }\}$ and $B=\{ru,v{u}^{\prime }\}$.

Suppose that there is a vertex $w^{\prime }$ such that $N\left(w\right)\cap N\left(w^{\prime }\right)=\varnothing$ and branches $B\left[w\right]$, $B\left[w^{\prime }\right]$ are isomorphic. Let $v^{\prime }\in N\left(w^{\prime }\right)$ be the vertex of $(r,w^{\prime })$-path. Then we write $A=\{vw,v^{\prime }{w}^{\prime }\}$ and $B=\{v{w}^{\prime },v^{\prime }w\}$.

Suppose that there is a vertex $u\ne v$ such that $(r,v)$-path according to $w$ and $(r,u)$-path according to $u^{\prime }$ are twins, where $u^{\prime }\in N\left(u\right)$ and $u^{\prime }$ is not a vertex of $(r,u)$-path. Then we set $A=\{vw,u{u}^{\prime }\}$ and $B=\{v{u}^{\prime },uw\}$.

Finally, let $d=3$, $e=rw$ and there is a leaf $l\notin B\left[w\right]$ such that $d(r,l)\in \{1,2\}$ or $(u,u^{\prime })$-path is symmetric according to $l$, where $ru$, $u^{\prime }l\in E$. Then $A=\{rw,rs\}$, where $s\ne w$, $s\ne u$ and $B=\{lw,ls\}$.

Necessity. Let $e\in E$. No vertices incident with $e$ are leaves. Since we assume that $T_d$ is 2-swappable, for that edge $e$ we have sets $A_e$, $B_e$ such that $e\in A_e\subset E$, $\left|A_e\right|\le 2$, $B_e\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$ and $(V,(E\setminus A_e)\cup B_e)\cong T_d$. In the proof for that edge $e$ we will consider every set $A$ such that $e\in A$ and $\left|A\right|\le 2$. For every chosen set $A$ we will reflect on every possible set $B$ such that $B\subset \left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E$ and $(V,(E\setminus A)\cup B)\cong T_d$. In every case, for every considered sets $A$ and $B$ we will obtain that one of conditions (i)–(vi) holds. Since the proper sets $A_e$ and $B_e$ are among considered pairs of sets $A$ and $B$ we will obtain that for that edge $e$ at least one of the conditions (i)–(vi) holds.

We will consider possibilities of choosing $A$ and then of choosing $B$. In every case $\sigma$ denotes isomorphic mapping of $T_d$ on vertices of a new $d$-nary tree $(V,(E\setminus A)\cup B)$. By $\sigma \left(T_u\left[v\right]\right)$ we will denote the image of $T_u\left[v\right]$ by isomorphic mapping $\sigma$, that is the twig pointed by $\sigma \left(v\right)$ and determined by $\sigma \left(u\right)$ in $d$-nary tree $(V,(E\setminus A)\cup B)$.

Case 1. One vertex incident with $e$ is the root $r$.

Denote $e=r{v}_1$, $deg\left(v_1\right)=d+1\ge 4$. We have to consider five different types of the set $A$: $\left\{r{v}_1\right\}$, $\{r{v}_1,r{w}_1\}$, $\{r{v}_1,v_1{v}_2\}$, $\{r{v}_1,v_i{v}_{i+1}\}$ where $i\ge 2$, $d(r,v_l)=l$, $l\in \{1,2,i,i+1\}$, $v_1$, $v_i$ are vertices of $(r,v_{i+1})$-path, $\{r{v}_1,w_j{w}_{j+1}\}$ where $j\ge 1$, $d(r,w_l)=l$, $l\in \{j,j+1\}$, $v_1$ is not a vertex of $(r,w_{j+1})$-path. In every case we try to choose the set $B$. Observe that, except for $d=3$ and $A=\{r{v}_1,r{w}_1\}$, in every case new edges have to join only vertices of deleted edges and only one of that vertices could became a new root. No leaf could became a new root. We can construct a new $d$-nary tree for the last two types of $A$ and for the second one for $d=3$.

Subcase 1.1. $A=\{r{v}_1,v_i{v}_{i+1}\}$, $i\ge 2$, $d(r,v_l)=l$, $l\in \{i,i+1\}$, $v_1$, $v_i$ are vertices of $(r,v_{i+1})$-path.

Let $v_k$ denote the vertex of $(r,v_{i+1})$-path such that $d(v,v_k)=k$, $k=1,\dots ,i+1$. We have two possibilities of choosing $B$: $\{r{v}_i,v_1{v}_{i+1}\}$ or $\{r{v}_i,r{v}_{i+1}\}$. Let us first suppose that $B=\{r{v}_i,v_1{v}_{i+1}\}$. Then $\sigma \left(r\right)=r$. Set $W=\{w_1:w_1\ne v_1,r{w}_1\in E,B\left[v_1\right]\cong B\left[w_1\right]\}$. It is clear that $\sigma \left(v_1\right)\in W\cup \left\{v_i\right\}$ and for every $w_1\in W$, $\sigma \left(w_1\right)\in W\cup \left\{v_i\right\}$. Hence without loss of generality we may assume that $\sigma \left(v_1\right)=v_i$.

We will ask which vertices of $(r,v_{i+1})$-path satisfy property: $\sigma \left(v_k\right)=v_{i+1-k}$, $1\le k\le i$. Observe that for $k=1$ the property is satisfied. Let us consider $\bar{k}\in \{1,\dots ,i\}$ such that $\sigma \left(v_{\bar{k}}\right)=v_{i+1-\bar{k}}$. It is easy to see that then $\sigma \left(v_k\right)=v_{i+1-k}$ for every $k\in \{1,\dots ,\bar{k}\}$. Observe that for $k\le \bar{k}-1$ we have that $\sigma \left(T_{v_{i+1}}\left[v_i\right]\right)\cong T_v\left[v_{i+1-k}\right]$. Therefore $T_{v_{i+1}}\left[v_i\right]\cong T_{v_{i+1}}\left[v_{i+1-k}\right]$ for $k\le \bar{k}-1$. If $\bar{k}-1\ge \lfloor \frac{i}{2}\rfloor$ we obtain that $(v_1,v_i)$-path is symmetric (according to $v_{i+1}$) and hence $e=r{v}_1$ satisfies condition (i). Let $\bar{k}-1<\lfloor \frac{i}{2}\rfloor$ and $\sigma \left(v_{\bar{k}+1}\right)\ne v_{i-\bar{k}}$. Then $\sigma \left(v_{\bar{k}+1}\right)$ is a vertex of $T_{v_{i+1}}\left[v_{i+1-\bar{k}}\right]$. Let us consider $\sigma \left(T_{v_{i+1}}\left[v_{\bar{k}}\right]\right)$. Observe that the set of vertices of $T_{v_{i+1}}\left[v_{\bar{k}}\right]$ and, moreover, vertices $v_1$, …,$v_{\bar{k}}$ are vertices of $\sigma \left(T_{v_{i+1}}\left[v_{\bar{k}}\right]\right)$. For that $T_{v_{i+1}}\left[v_{\bar{k}}\right]$, $\sigma \left(T_{v_{i+1}}\left[v_{\bar{k}}\right]\right)$ are isomorphic and have different number of vertices, a contradiction.

Let $B=\{r{v}_i,r{v}_{i+1}\}$. Then $\sigma \left(r\right)=v_1$. Let us suppose that for every $k\in \{1,\dots ,i-1\}$ we have $\sigma \left(v_k\right)=v_{k+1}$. Then $\sigma \left(T_{v_{i+1}}\left[v_k\right]\right)\cong T_{v_{i+1}}\left[v_{k+1}\right]$, $1\le k\le i-1$ and then $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+1}\right]$, $1\le k\le i-1$. Since $\sigma \left(r\right)=v_1$ and hence $\sigma \left(T_{v_{i+1}}\left[r\right]\right)\cong T_{v_{i+1}}\left[v_1\right]$ we obtain that $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_k\right]$, $1\le k\le i$. Especially, $(r,v_i)$-path is symmetric according to $v_{i+1}$ and $e=r{v}_1$ satisfies (i). Let us suppose that there is $k_0\in \{1,\dots ,i-2\}$ such that $\sigma \left(v_{k_0}\right)=v_{k_0+1}$, $\sigma \left(v_{k_0+1}\right)\ne v_{k_0+2}$. It is easy to see that $\sigma \left(v_k\right)=v_{k+1}$, $k\le k_0$ and, like previously, we obtain that $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_k\right]$, $k\le k_0+1$. We have that $\sigma \left(v_{k_0+1}\right)$ is the vertex of $T_{v_{i+1}}\left[v_{k_0+1}\right]$. Observe that $v_i$ and vertices of $T_{v_1}\left[r\right]$ are vertices of $\sigma \left(T_{v_{i+1}}\left[v_{k_0}\right]\right)$, contrary to that $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_{k_0}\right]$. Similarly we obtain that it is impossible that $\sigma \left(v_1\right)\ne v_2$.

Subcase 1.2. $A=\{r{v}_1,w_i{w}_{i+1}\}$, $i\ge 1$, $d(r,w_l)=l$, $l\in \{i,i+1\}$ $v_1$, $w_i$ are vertices of $(r,w_{i+1})$-path.

In this subcase $B=\{r{w}_{i+1},v_1{w}_i\}$. Then $\sigma \left(r\right)=r$ and like in Subcase 1.1., using the set $W$, we can assume that $\sigma \left(w_{i+1}\right)=v_1$. Hence $B\left[v_1\right]\cong B\left[w_{i+1}\right]$ and $e$ satisfies (iv).

Subcase 1.3. $A=\{r{v}_1,r{w}_1\}$, $d=3$, $d(r,w_1)=1$.

Then $B=\{l{v}_1,l{w}_1\}$, where $l$ is a leaf and $l\notin B\left[v_1\right]$, $l\notin B\left[w_1\right]$. Then $\sigma \left(r\right)=l$. If $rl\in E$ then $e=r{v}_1$ satisfies (vi). Let $u_1\in N\left(r\right)\setminus \{v_1,w_1\}$, $deg\left(u_1\right)=4$. Like in Subcase 1.1. we may assume that $\sigma \left(v_1\right)=v_1$, $\sigma \left(w_1\right)=w_1$ and $\sigma \left(u_1\right)=u_1$. Moreover, using the same arguments as in Subcase 1.1. we can prove that $\sigma \left(l\right)=r$ and $(u_1,u)$-path is symmetric according to $l$, where $ul\in E$, and hence $e=r{v}_1$ satisfies (vi).

Case 2. The edge $e$ is not incident with the root.

Denote $e=v_i{v}_{i+1}$, $i\ge 1$, $d\left(v_i\right)=d\left(v_{i+1}\right)=d+1\ge 4$, $d(r,v_l)=l$, $l\in \{i,i+1\}$. Let $v_k$ denote the vertex of $(r,v_{i+1})$-path such that $d(r,v_k)=k$, $k=1,\dots ,i+1$.

Subcase 2.1. $A=\left\{v_i{v}_{i+1}\right\}$.

To obtain isomorphic $d$-nary tree we have to choose $B=\left\{r{v}_{i+1}\right\}$. Then $\sigma \left(r\right)=v_i$. If $\sigma \left(v_i\right)\ne r$ then there is a vertex $w$ of $T_d$ such that $v_{i}w\notin E$, $B\left[w\right]\cong B\left[v_{i+1}\right]$ and $v_i{v}_{i+1}$ satisfies (iv). Hence we may assume that $\sigma \left(v_i\right)=r$ and then, like in Subcase 1.1., $\sigma \left(v_k\right)=v_{i-k}$, $k=1,\dots ,i-1$. Hence $(r,v_i)$-path is symmetric according to $v_{i+1}$ and $e$ satisfies (i).

Subcase 2.2. $A=\{v_i{v}_{i+1},v_{i+1}{v}_{i+2}\}$, where $d(r,v_{i+2})=i+2$.

Then $B=\{r{v}_{i+1},v_i{v}_{i+2}\}$ and $\sigma \left(r\right)=v_{i+1}$. Like in Subcase 2.1. if $\sigma \left(v_{i+2}\right)\ne v_i$ then $v_i{v}_{i+1}$ satisfies (iv). Let $\sigma \left(v_{i+1}\right)=v_i$. Then $\sigma \left(v_1\right)=r$, $\sigma \left(v_k\right)=v_{k-1}$, $k=1,\dots ,i+1$. Observe that $\sigma \left(T_{v_{i+1}}\left[v_k\right]\right)\cong T_{v_{i+1}}\left[v_{k-1}\right]$, $k\le i$, $\sigma \left(T_{v_{i+1}}\left[v_1\right]\right)\cong T_{v_{i+1}}\left[r\right]$. Hence $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_k\right]$, $k<i$ and especially $(r,v_i)$-path is symmetric according to $v_{i+1}$ and $e=v_i{v}_{i+1}$ satisfies (i).

Subcase 2.3. $A=\{v_i{v}_{i+1},v_j{v}_{j+1}\}$, $j\ge i+2$, $d(r,v_l)=l$, $l\in \{i,i+1,j,j+1\}$.

We have several possibilities of choosing $B$: $\{v_i{v}_j,v_{i+1}{v}_{j+1}\}$, $\{r{v}_j,v_{i+1}{v}_{j+1}\}$, $\{r{v}_{i+1},v_i{v}_{j+1}\}$, $\{r{v}_{j+1},v_i{v}_j\}$, $\{r{v}_j,v_i{v}_{j+1}\}$. Edges in $B$ join only vertices $r$, $v_i$, $v_{i+1}$, $v_j$, $v_{j+1}$. For chosen sets $A$, $B$ let us reflect on branches of $T_d$ and branches of the new $d$-nary tree $(V,(E\setminus A)\cup B)$. Since $T_d$ and $(V,(E\setminus A)\cup B)$ are isomorphic, we obtain that families of branches pointed by all vertices from V are the same in both trees. Observe that if $w$ is not a vertex of $(r,v_j)$-path then the branch pointed by $w$ in $T_d$ is isomorphic to the branch pointed by $w$ in $(V,(E\setminus A)\cup B)$. For this reason the families of branches pointed by vertices of $(r,v_j)$-path in $T_d$ and $(V,(E\setminus A)\cup B)$ are the same. Moreover, in $T_d$ branches pointed by vertices of $(r,v_j)$-path have a property: for $\bar{k}\ge 1$, $B\left[v_{\bar{k}}\right]$ is a subgraph of $B\left[r\right]$ and of $B\left[v_k\right]$, $k\in \{1,\dots ,\bar{k}-1\}$. Hence branches pointed by vertices of $(r,v_j)$-path in $(V,(E\setminus A)\cup B)$ should have the same property.

I. $B=\{v_i{v}_j,v_{i+1}{v}_{j+1}\}$.

Then $\sigma \left(r\right)=r$ and, by remark about branches, we can deduce that $(v_j,v_{i+1})$-path according to $v_{j+1}$ and $(v_{i+1},v_j)$-path according to $v_{j+1}$ are twins. Hence $(v_{i+1},v_j)$-path is symmetric according to $v_{j+1}$ and $v_i{v}_{i+1}$ satisfies (i).

II. $B=\{r{v}_j,v_{i+1}{v}_{j+1}\}$.

Then $\sigma \left(r\right)=v_i$. By remark about branches we have that $(r,v_i)$-path and $(v_i,r)$-path, both according to $v_{i+1}$, are twins and hence $(r,v_i)$-path is symmetric according to $v_{i+1}$.

III. $B=\{r{v}_{i+1},v_i{v}_{j+1}\}$.

Then $\sigma \left(r\right)=v_j$. We reflect on $i+1\ge 2$ vertices of $(r,v_i)$-path and $j-i\ge 2$ vertices of $(v_{i+1},v_j)$-path. We will find which paths are twins. Every pair of twins path in $T_d$ is taken according to $v_{j+1}$. Let us first suppose that $i+1=j-i$. Then by remark about branches, $(v_j,v_{i+1})$-path and $(r,v_i)$-path are twins. We also have that $(r,v_i)$-path and $(v_{i+1},v_j)$-path are twins. From above we obtain that $(v_{i+1},v_j)$-path is symmetric according to $v_{j+1}$ and hence $(r,v_i)$-path is symmetric according to $v_{i+1}$ and $e$ satisfies (i).

Assume that $i+1>j-i$. Observe that $(r,v_{j-i-1})$-path and $(v_j,v_{i+1})$-path are twins. We also have that $(v_{j-i},v_j)$-path and $(r,v_i)$-path are twins. Especially, their proper parts: $(v_{i+1},v_j)$-path and $(v_{2i-j+1},v_i)$-path are twins, and hence $(r,v_{j-i-1})$-path and $(v_i,v_{2i-j+1})$-path are twins. We consider vertices of $(r,v_i)$-path. From above we also obtain that $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+(j-i)}\right]$, $k=1,\dots ,2i-j$, that is $(r,v_{2i-j})$-path and $(v_{2i-j+1},v_i)$-path are twins. Moreover, we can observe that $(v_{j-i},v_{2(j-i)-1})$-path and $(r,v_{j-i-1})$-path are twins, too and so on. Hence we have that $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k+(j-i)}\right]$, where $k=1,\dots ,i-(j-i)$. Let $i+1=n(j-i)+\alpha$, where $n$, $\alpha$ are natural numbers such that $n\ge 1$, $0\le \alpha <j-i$. Observe that $(v_{(n-1)(j-i)},v_i)$-path is symmetric according to $v_{i+1}$ and $v_i{v}_{i+1}$ satisfies (i).

Suppose that $i+1<j-i$. We notice that $(r,v_i)$-path and $(v_j,v_{j-(i+1)})$-path are twins. Then we consider $(v_{i+1},v_j)$-path and observe that $(v_{j-(i+1)},v_j)$-path and $(r,v_i)$-path are twins. Hence $(v_i,r)$-path is symmetric according to $v_{i+1}$.

IV. $B=\{r{v}_{j+1},v_i{v}_j\}$.

Then $\sigma \left(r\right)=v_{i+1}$. We consider $i+1\ge 2$ vertices of $(r,v_i)$-path and $j-i\ge 2$ vertices of $(v_{i+1},v_j)$-path. We will find twins paths. Every path in $T_d$ will be taken according to $v_{j+1}$.

Let us first suppose that $i+1<j-i$. Then $(r,v_{j-i-1})$-path and $(v_{i+1},v_j)$-path are twins. We also have that $(v_{j-i},v_j)$-path and $(v_i,r)$-path are twins. Especially, $(v_{j-i},v_j)$-path and $(v_{2i+1},v_{i+1})$-path are twins. From above we obtain that $(r,v_i)$-path and $(v_{i+1},v_{2i+1})$-path are twins and, moreover, $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k+(i+1)}\right]$, $k=1,\dots ,j-i-1$. Because of the structure of twigs of the first and of the last $i+1$ vertices of $(v_{i+1},v_j)$-path we obtain that $(v_{i+1},v_j)$-path is symmetric according to $v_{j+1}$.

Suppose that $i+1\ge j-i$. Then $(r,v_{j-i-1})$-path and $(v_{i+1},v_j)$-path are twins and $(v_{i+1},v_j)$-path and $(v_{j-i-1},r)$-path are twins. Then $(v_{i+1},v_j)$-path is symmetric according to $v_{j+1}$ and $v_i{v}_{i+1}$ satisfies (i).

V. $B=\{r{v}_j,v_i{v}_{j+1}\}$.

We consider $i+1\ge 2$ vertices of $(r,v_i)$-path and $j-i\ge 2$ vertices of $(v_{i+1},v_j)$-path. It is obvious that $\sigma \left(r\right)=v_{i+1}$. We will find twins paths. Every pair of twins paths in $T_d$ is taken according to $v_{j+1}$. By the remark about branches we have that $(r,v_{j-i-1})$-path, $(v_{i+1},v_j)$-path are twins and $(v_{j-i},v_j)$-path, $(r,v_i)$-path are twins.

Let us first suppose that $i+1\le j-i$. Then for $(r,v_i)$-path we obtain that $(v_{j-i},v_j)$-path and $(r,v_i)$-path are twins. For $(v_{i+1},v_j)$-path we obtain that $(r,v_i)$-path and $(v_{i+1},v_{2i+2})$-path are twins. Hence we have that $(r,v_i)$-path, $(v_{i+1},v_{2i+2})$-path are twins and $v_i{v}_{i+1}$ joins twins paths.

Suppose that $i+1>j-i$. For $(v_{i+1},v_j)$-path we have that $(r,v_{j-i-1})$-path, $(v_{i+1},v_j)$-path are twins. For $(r,v_i)$-path we know that $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+(j-i)}\right]$, $k=1,\dots ,i-(j-i)$, $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_{j-i}\right]$ and $(v_{i+1},v_j)$-path, $\left(v_{i-(j-i)+1}{v}_i\right)$-path are twins.

From now we will consider $(r,v_i)$-path. From above we obtain that $(r,v_{j-i-1})$-path, $(v_{i-(j-i)+1},v_i)$-path are twins and $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+(j-i)}\right]$, $k=1,\dots ,i-(j-i)$, $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_{j-i}\right]$. Let $i+1=n(j-i)+{\alpha }_1$, where $n$, ${\alpha }_1$ are natural numbers such that $n\ge 1$, $0\le {\alpha }_1<j-i$. If ${\alpha }_1=0$ then it is easy to see that $n\ge 2$ and $(r,v_i)$-path is sequential according to $v_{i+1}$. Assume that ${\alpha }_1\in (0,j-i)$. Using properties of $(r,v_i)$-path we will describe its twigs, first starting with $r$ and going to $v_i$ and then starting with $v_i$ and going to $r$. In the first way we obtain that $T_{v_{i+1}}\left[v_{t(j-i)}\right]\cong T_{v_{i+1}}\left[r\right]$, $T_{v_{i+1}}\left[v_{k+t(j-i)}\right]\cong T_{v_{i+1}}\left[v_k\right]$, $t\in \{0,\dots ,n\}$, $k\in \{1,\dots ,j-i-1\}$, $T_{v_{i+1}}\left[v_{s+n(j-i)}\right]\cong T_{v_{i+1}}\left[v_s\right]$, $s\in \{1,\dots ,{\alpha }_1-1\}$. In the other way we obtain that $T_{v_{i+1}}\left[v_{{\alpha }_1+t(j-i)}\right]\cong T_{v_{i+1}}\left[r\right]$, $T_{v_{i+1}}\left[v_{k+{\alpha }_1+t(j-i)}\right]\cong T_{v_{i+1}}\left[v_k\right]$, $t\in \{0,\dots ,n-1\}$, $k\in \{1,\dots ,j-i-1\}$, $T_{v_{i+1}}\left[v_{j-i-{\alpha }_1+s}\right]\cong T_{v_{i+1}}\left[v_s\right]$, $s\in \{1,\dots ,{\alpha }_1-1\}$, $T_{v_{i+1}}\left[v_{j-i-{\alpha }_1}\right]\cong T_{v_{i+1}}\left[r\right]$. Comparing these results we observe that $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_{t(j-i)}\right]\cong T_{v_{i+1}}\left[v_{n(j-i)}\right]\cong T_{v_{i+1}}\left[v_{{\alpha }_1+t(j-i)}\right]$, $t\in \{1,\dots ,n-1\}$, $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+s(j-i)}\right]\cong T_{v_{i+1}}\left[v_{k+{\alpha }_1+s(j-i)}\right]$, $s\in \{0,\dots ,n-1\}$, $k\in \{1,\dots ,j-i-1\}$ and hence $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+{\alpha }_1}\right]$, $k\in \{1,\dots ,i-{\alpha }_1\}$. Moreover, $(r,v_{{\alpha }_1-1})$-path and $(v_{n(j-i)},v_{n(j-i)+{\alpha }_1-1})$-path ($(v_{n(j-i)},v_i)$-path) are twins. Let $i+1=m{\alpha }_1+{\alpha }_2$, where $m$, ${\alpha }_2$ are natural numbers such that $m\ge 1$, $0\le {\alpha }_2<{\alpha }_1$. If ${\alpha }_2=0$, then $m\ge 2$ and $(r,v_i)$-path is sequential according to $v_{i+1}$. If ${\alpha }_2>0$ we will repeat reasoning above replacing $j-i$ by ${\alpha }_1$ and ${\alpha }_1$ by ${\alpha }_2$. In every step we have the remainder less than the one in previous step. Hence there are the natural numbers ${\alpha }_s$, $t$ such that $i+1=t{\alpha }_s$, and finally $(r,v_i)$-path is sequential according to $v_{i+1}$ the edge $v_i{v}_{i+1}$ satisfies (iii).

Subcase 2.4. $A=\{v_i{v}_{i+1},v_{i-1}{v}_i\}$, $i\ge 1$ and $(r,\dots ,v_{i-1},v_i,v_{i+1})$ is $(r,v_{i+1})$-path.

Observe that if $i=1$ and $v_{i-1}=r$ it is impossible to fix the set $B$ and a new $d$-nary tree. Assume that $i\ge 2$. Then $B=\{r{v}_i,v_{i-1}{v}_{i+1}\}$ and $\sigma \left(r\right)=v_i$.

Let us suppose that $\sigma \left(v_i\right)\ne v_{i-1}$. Then $w=\sigma \left(v_{i+1}\right)$ is not a vertex of $(r,v_{i-1})$-path and $w\ne v_{i+1}$. Since $\sigma \left(v_i\right)\ne v_i$, we have that $w\notin N\left(v_i\right)$. We have that $B\left[w\right]\cong B\left[v_{i+1}\right]$. Hence $v_i{v}_{i+1}$ satisfies (iv).

Therefore we may assume that $\sigma \left(v_i\right)=v_{i-1}$. Then $\sigma \left(v_1\right)=r$, $\sigma \left(v_k\right)=v_{k-1}$, $k=2,\dots ,i$. Hence $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_k\right]$, $k=1,\dots ,i$ and especially $(r,v_i)$-path is symmetric according to $v_{i+1}$ and $v_i{v}_{i+1}$ satisfies (i).

Subcase 2.5. $A=\{v_i{v}_{i+1},v_j{v}_{j+1}\}$, $1\le j\le i-2$ and $(r,\dots ,v_j,v_{j+1},\dots ,v_i,v_{i+1})$ is $(r,v_{i+1})$-path.

We have some possibilities of choosing $B$.

I. $B=\{v_j{v}_i,v_{j+1}{v}_{i+1}\}$.

Then $\sigma \left(r\right)=r$. Observe that it is impossible that $\sigma \left(v_i\right)=v_i$.

If $\sigma \left(v_i\right)\ne v_{j+1}$ then $w=\sigma \left(v_{i+1}\right)$ is not a vertex of $(r,v_i)$-path and $w\ne v_{i+1}$, $w\notin N\left(v_i\right)$, $B\left[w\right]\cong B\left[v_{i+1}\right]$. Hence $v_i{v}_{i+1}$ satisfies (iv).

Therefore we may assume that $\sigma \left(v_i\right)=v_{j+1}$. Then $\sigma \left(v_{j+1}\right)=v_i$, $\sigma \left(v_{j+1+k}\right)=v_{i-k}$, $k=1,\dots ,i-j-1$, ($\sigma \left(v_i\right)=v_{j+1}$). Hence $(v_{j+1},v_i)$-path is symmetric according to $v_{i+1}$.

II. $B=\{r{v}_i,v_{j+1}{v}_{i+1}\}$.

Then $\sigma \left(r\right)=v_j$. Similarly as in I., $\sigma \left(v_i\right)\ne v_i$ and if $\sigma \left(v_i\right)\ne v_{j+1}$ then $v_i{v}_{i+1}$ satisfies (iv). We may assume that $\sigma \left(v_i\right)=v_{j+1}$ and then $\sigma \left(v_{j+k}\right)=v_{i-(k-1)}$, $k=1,\dots ,i-j$, ($\sigma \left(v_{j+1}\right)=v_i$, $\sigma \left(v_i\right)=v_{j+1}$). Hence $(v_{j+1},v_i)$-path is symmetric according to $v_{i+1}$.

III. $B=\{r{v}_{j+1},v_j{v}_{i+1}\}$.

Then $\sigma \left(r\right)=v_i$. If $\sigma \left(v_i\right)\ne v_j$ then $w=\sigma \left(v_{i+1}\right)$ is not a vertex of $(r,v_i)$-path, $w\ne v_{i+1}$, $w\notin N\left(v_i\right)$, $B\left[w\right]\cong B\left[v_{i+1}\right]$ and hence $v_i{v}_{i+1}$ satisfies (iv).

Let $\sigma \left(v_i\right)=v_j$. Then $\sigma \left(v_k\right)=v_{i-k}$, $k=1,\dots ,i-j-1$, $\sigma \left(v_{i-j}\right)=r$, $\sigma \left(v_{i-j+l}\right)=v_l$, $l=1,\dots ,j$ and hence $(r,v_{i-j-1})$-path, $(v_i,v_{j+1})$-path are twins and $(v_{i-j},v_i)$-path, $(r,v_j)$-path are twins, in every case according to $v_{j+1}$. We consider $j+1\ge 2$ vertices of $(r,v_j)$-path and $i-j$ vertices of $(v_{j+1},v_i)$-path. Twins paths which we will find in $T_d$, we will take according to $v_{i+1}$.

Suppose that $j+1\ge i-j$. Then we have that $(r,v_j)$-path and $(v_i,v_{i-(j+1)})$-path are twins and also $(v_{i-(j+1)},v_i)$-path and $(r,v_j)$-path are twins. Hence $(v_{i-(j+1)},v_i)$-path is symmetric according to $v_{i+1}$ and $v_i{v}_{i+1}$ satisfies (i).

Suppose that $i-j>j+1$. Then we have that $(r,v_{i-j-1})$-path and $(v_i,v_{j+1})$-path are twins and also $(v_{i-j},v_i)$-path and $(r,v_j)$-path are twins. From above we obtain that $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+(i-j)}\right]$, $k=1,\dots ,j$, $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_{i-j}\right]$. Let us consider $i+1$ vertices of $(r,v_i)$-path. Let $i+1=n(i-j)+\alpha$, where $n$, $\alpha$ are natural numbers such that $n\ge 1$, $0\le \alpha <i-j$. Observe that $(v_{(n-1)(i-j)},v_i)$-path is symmetric according to $v_{i+1}$ and $v_i{v}_{i+1}$ satisfies (i).

IV. $B=\{r{v}_{i+1},v_j{v}_i\}$.

Then $\sigma \left(r\right)=v_{j+1}$. Once again, if $\sigma \left(v_i\right)\ne r$, then, since it is obvious that $\sigma \left(v_i\right)\ne v_i$, $v_i{v}_{i+1}$ satisfies (iv). Let $\sigma \left(v_i\right)=r$. Then $(r,v_{i-j+1})$-path, $(v_{j+1},v_i)$-path are twins, both according to $v_{i+1}$ and $(v_{i-j},v_i)$-path, $(r,v_j)$-path are twins, both according to $v_{i+1}$. We repeat arguments of Subcase 2.3.IV. replacing $v_j$ by $v_i$, $v_{j+1}$ by $v_{i+1}$, $v_i$ by $v_j$, $v_{i+1}$ by $v_{j+1}$ and obtain that $(v_{j+1},v_i)$-path is symmetric according to $v_{i+1}$.

V. $B=\{r{v}_i,v_j{v}_{i+1}\}$.

Then $\sigma \left(r\right)=v_{j+1}$ and it is impossible that $\sigma \left(v_i\right)=v_i$. If $\sigma \left(v_i\right)\ne v_j$ we obtain that $v_i{v}_{i+1}$ satisfies (iv). Let us assume that $\sigma \left(v_i\right)=v_j$. Then $\sigma \left(v_k\right)=v_{j+1+k}$, $k=1,\dots ,i-j-1$, $\sigma \left(v_{i-j}\right)=r$, $\sigma \left(v_{i-j+t}\right)=v_t$, $t=1,\dots ,j$. We consider $(r,v_j)$-path of $j+1$ vertices and $(v_{j+1},v_i)$-path of $i-j$ vertices. In Subcase 2.3.V. we consider $(x_1,x_{u+1})$-path such that $T_{x_{u+1}}\left[x_k\right]\cong T_{x_{u+1}}\left[x_{k+w}\right]$, $k=1,\dots ,u-w$ and $(x_1,x_w)$-path, $(x_{u-w+1},x_u)$-path are twins, both according to $x_{u+1}$ where $w\le u$. We proved that if $u=u_{1}w+{\alpha }_1$, where $u_1$, ${\alpha }_1$ are nonnegative integers, $u_1\ge 1$, ${\alpha }_1\in (0,w)$ then $(x_1,x_u)$-path has properties: $T_{x_{u+1}}\left[x_k\right]\cong T_{x_{u+1}}\left[x_{k+{\alpha }_1}\right]$, $k=1,\dots ,u-{\alpha }_1$, $(x_1,x_{{\alpha }_1})$-path, $(x_{u-{\alpha }_1+1},x_u)$-path are twins, both according to $x_{u+1}$.

If ${\alpha }_1=0$, then $u_1\ge 2$ and $(x_1,x_u)$-path is sequential according to $x_{u+1}$. Let $d$ be the greatest common divisor of $u$ and $w$. Observe that $d$ is a divisor of ${\alpha }_1$, too. We can repeat the arguments for $u$ and ${\alpha }_1$ and obtain that either $u=u_2{\alpha }_1$ and $(x_1,x_u)$-path is sequential according to $x_{u+1}$ or $u=u_2{\alpha }_1+{\alpha }_2$, ${\alpha }_2\in (0,{\alpha }_1)$, $T_{x_{u+1}}\left[x_k\right]\cong T_{x_{u+1}}\left[x_{k+{\alpha }_2}\right]$, $(x_1,x_{{\alpha }_2})$-path, $(x_{u-{\alpha }_2+1},x_u)$-path are twins, both according to $x_{u+1}$ and $d$ is a divisor of ${\alpha }_2$. Since in every step we have the remainder less than the one in a previous step, then after several steps we obtain that there is ${\alpha }_s$ such that $u=u_{s-1}{\alpha }_s$, $u_{s-1}$, ${\alpha }_s$ are positive integers, $d$ is a divisor of ${\alpha }_s$ and $(x_1,x_u)$-path is sequential according to $x_{u+1}$.

In the following part of V. considered path (in $T_d$) are taken according to $v_{i+1}$.

Assume that $j+1\ge i-j$. The mapping $\sigma$ courses that $(v_{j+1},v_i)$-path, $(r,v_{i-j-1})$-path are twins and $T_{v_{j+1}}\left[r\right]\cong T_{v_{j+1}}\left[v_{i-j}\right]$, $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k-(i-j)}\right]$, $k=i-j+1,\dots ,i$, $(v_{j-(i-j)+1},v_j)$-path, $(v_{j+1},v_i)$-path are twins.

Let $d$ be the greatest common divisor of $j+1$ and $i-j$. First we look at $(r,v_j)$-path and use described above procedure. We obtain that there is a positive integer ${\alpha }_1$ such that $j+1=n_1{\alpha }_1$, $d$ is a divisor of ${\alpha }_1$ and $T_{v_{j+1}}\left[r\right]\cong T_{v_{j+1}}\left[v_{{\alpha }_1}\right]$, $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k+{\alpha }_1}\right]$, $k=1,\dots ,j+1-{\alpha }_1$. We turn back to $(v_{j+1},v_i)$-path. The mapping $\sigma$ courses that $(v_{j+1},v_i)$-path, $(r,v_{i-j-1})$-path are twins. Hence $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+{\alpha }_1}\right]$, $k=j+1,\dots ,i-{\alpha }_1$ and $(v_{j+1},v_{j+{\alpha }_1})$-path, $(r,v_{{\alpha }_1-1})$-path are twins and $(v_{i-{\alpha }_1+1},v_i)$-path, $(v_{i-j-{\alpha }_1},v_{i-j-1})$-path are twins. Vertices of $(v_{i-j-{\alpha }_1},v_{i-j-1})$-path are vertices of $(r,v_j)$-path, too. Hence $(v_{i-j-{\alpha }_1},v_{i-j-1})$-path, $(v_{i-j},v_{i-j-1+{\alpha }_1})$-path are twins. Moreover, for $(r,v_j)$-path we have that $(v_{i-j},v_{i-j-1+{\alpha }_1})$-path, $(r,v_{{\alpha }_1-1})$-path are twins. We conclude that $(v_{j+1},v_{j+{\alpha }_1})$-path, $(v_{i-{\alpha }_1+1},v_i)$-path are twins and $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+{\alpha }_1}\right]$, $k=j+1,\dots ,i-{\alpha }_1$.

Let $i-j=m{\alpha }_1+\beta$, where $m$, $\beta$ are nonnegative integers and $0\le \beta <{\alpha }_1$. If $\beta =0$, then $(r,v_i)$-path is sequential. If $\beta >0$, then $d$ is a divisor of $\beta$ and we repeat procedure of finding the positive number ${\beta }_1$ such that $i-j=m_1{\beta }_1$, $d$ is a divisor of ${\beta }_1$ and $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+{\beta }_1}\right]$, $k=j+1,\dots ,i-{\beta }_1$.

It is clear that ${\beta }_1<{\alpha }_1$. We check $(r,v_j)$-path. Observe that properties associated with the value $i-j$ follow the same for ${\beta }_1$, that is, $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k+{\beta }_1}\right]$, $k=1,\dots ,j-{\beta }_1$, $T_{v_{j+1}}\left[r\right]\cong T_{v_{j+1}}\left[v_{{\beta }_1}\right]$, $(r,v_{{\beta }_1-1})$-path, $(v_{j-{\beta }_1+1},v_j)$-path are twins.

Let $j+1=n{\beta }_1+\alpha$ where $n$, $\alpha$ are nonnegative integers $0\le \alpha <{\beta }_1$. If $\alpha =0$, then $(r,v_i)$-path is sequential. If $\alpha >0$, then we once more use described procedure and obtain that there is a positive integer ${\alpha }_2$ such that $j+1=n_2{\alpha }_2$, $d$ is a divisor of ${\alpha }_2$ and $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k+{\alpha }_2}\right]$, $k=1,\dots ,j-{\alpha }_2$, $T_{v_{j+1}}\left[r\right]\cong T_{v_{j+1}}\left[v_{{\alpha }_2}\right]$.

It is obvious that ${\alpha }_2<{\beta }_1$. Then we consider $(v_{j+1},v_i)$-path and so on. We obtain less and less positive integer with $d$ as a divisor. Hence finally we obtain that $T_{v_{i+1}}\left[v\right]\cong T_{v_{i+1}}\left[v_d\right]$, $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+d}\right]$, $k=1,\dots ,i-d$ and $(r,v_i)$-path is sequential, hence $v_i{v}_{i+1}$ satisfies (ii).

Assume that $j+1<i-j$. The mapping $\sigma$ for $(v_{j+1},v_i)$-path courses that $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+j+1}\right]$, $k=j+1,\dots ,i-j-1$, $(r,v_j)$-path, $(v_{j+1},v_{2j+1})$-path are twins, for $(r,v_j)$-path courses that $(v_{i-j},v_i)$-path, $(r,v_j)$-path are twins. Hence $(v_{j+1},v_{2j+1})$-path, $(v_{i-j},v_i)$-path are twins.

Let $d$ be the greatest common divisor of $j+1$ and $i-j$. If $d=j+1$, then $(r,v_i)$-path is sequential If $d<j+1$, then we obtain that there is a positive integer ${\beta }_1<j+1$ such that $i-j=m_1{\beta }_1$, $d$ is a divisor of ${\beta }_1$, $T_{v_{i+1}}\left[v_k\right]\cong T_{v_{i+1}}\left[v_{k+{\beta }_1}\right]$, $k=j+1,\dots ,i-{\beta }_1$.

Let us consider $(r,v_j)$-path. Since $(r,v_j)$-path, $(v_{j+1},v_{2j+1})$-path are twins we have that $T_{v_{j+1}}\left[r\right]\cong T_{v_{j+1}}\left[v_{{\beta }_1}\right]$, $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k+{\beta }_1}\right]$, $k=1,\dots ,j-{\beta }_1$ and $(r,v_{{\beta }_1})$-path, $(v_{j+1},v_{j+{\beta }_1})$-path are twins. Since $(v_{j+1},v_{j+{\beta }_1})$-path, $(v_{i-{\beta }_1-1},v_i)$-path and $(v_{i-{\beta }_1-1},v_i)$-path, $(v_{j-{\beta }_1-1},v_j)$-path are twins, we obtain that $(r,v_{{\beta }_1})$-path, $(v_{j-{\beta }_1-1},v_j)$-path are twins.

If ${\beta }_1$ is a divisor of $j+1$, then we obtain that $(r,v_i)$-path is sequential. If $d<{\beta }_1$, then there is a positive integer ${\alpha }_1<{\beta }_1$ such that $j+1=n_1{\alpha }_1$, $d$ is a divisor of ${\alpha }_1$, $T_{v_{j+1}}\left[r\right]\cong T_{v_{j+1}}\left[v_{{\alpha }_1}\right]$, $T_{v_{j+1}}\left[v_k\right]\cong T_{v_{j+1}}\left[v_{k+{\alpha }_1}\right]$, $k=1,\dots ,j-{\alpha }_1$. We repeat arguments again and again and finally obtain that $(r,v_i)$-path is sequential.

Subcase 2.6. $A=\{v_i{v}_{i+1},r{v}_1\}$, $i\ge 2$, $(r,v_1,\dots ,v_i,v_{i+1})$ is $(r,v_{i+1})$-path.

I. $B=\{r{v}_i,v_1{v}_{i+1}\}$.

Then $\sigma \left(r\right)=r$. If $\sigma \left(v_i\right)=v_1$ then $\sigma \left(v_k\right)=v_{i-(k-1)}$, $k=1,\dots ,i$ and hence $(v_1,v_i)$-path is symmetric according to $v_{i+1}$. If $\sigma \left(v_i\right)\ne v_1$ then $v_i{v}_{i+1}$ satisfies (iv).

II. $B=\{r{v}_i,r{v}_{i+1}\}$.

Then $\sigma \left(r\right)=v_1$. If $\sigma \left(v_i\right)=r$ then $\sigma \left(v_k\right)=v_{k+1}$, $k=1,\dots ,i-1$. Hence $T_{v_{i+1}}\left[r\right]\cong T_{v_{i+1}}\left[v_k\right]$, $k=1,\dots ,i$. Especially, $(r,v_i)$-path is sequential according to $v_{i+1}$. If $\sigma \left(v_i\right)\ne r$ then $v_i{v}_{i+1}$ satisfies (iv).

Subcase 2.7. $A=\{v_i{v}_{i+1},u_j{u}_{j+1}\}$, $i\ge 1$, $j\ge 1$, $u_j{u}_{j+1},v_i{v}_{i+1}\in E\left(B\left[v_1\right]\right)$, $u_j{u}_{j+1}\notin E\left(B\left[v_{i+1}\right]\right)$, $v_i{v}_{i+1}\notin E\left(B\left[v_{i+1}\right]\right)$, $(r,v_1,\dots ,v_s,v_{s+1},\dots ,v_i,v_{i+1})$ is $(r,v_{i+1})$-path, $(r,v_1,\dots ,v_s,u_{s+1},\dots ,u_j,u_{j+1})$ is $(r,u_{j+1})$-path, $1\le s$, $s\le i$, $s\le j$.

Observe that if $s=i=j$ it is impossible to create a new $d$-nary tree. We may assume that $s<i$ or $s<j$.

We have several possibilities of choosing $B$.

I. $B=\{v_i{u}_{j+1},u_j{v}_{i+1}\}$.

Then $\sigma \left(r\right)=r$. If $\sigma \left(v_i\right)=v_i$ then $B\left[u_{j+1}\right]$ has to be isomorphic to $B\left[v_{i+1}\right]$ and $v_i{v}_{i+1}$ satisfies (iv). If $\sigma \left(v_i\right)=u_j$ then $i=j$ and $(r,v_i)$-path according to $v_{i+1}$, $(r,u_j)$-path according to $u_{j+1}$ are twins. Hence $v_i{v}_{i+1}$ satisfies (v). If $\sigma \left(v_i\right)$ is not a vertex of $(r,v_i)$-path and is not a vertex of $(r,u_j)$-path then $\sigma \left(v_{i+1}\right)\ne v_{i+1}$, $\sigma \left(v_{i+1}\right)\notin N\left(v_i\right)$ and $B\left[\sigma \left(v_{i+1}\right)\right]\cong B\left[v_{i+1}\right]$. Hence $v_i{v}_{i+1}$ satisfies (iv).

II. $B=\{r{u}_{j+1},u_j{v}_{i+1}\}$.

Then $\sigma \left(r\right)=v_i$. If $\sigma \left(v_i\right)\ne u_j$ then $\sigma \left(v_{i+1}\right)\ne v_{i+1}$ and hence $v_{i+1}\notin N\left(\sigma \left(v_i\right)\right)$. Therefore there is a vertex $w$ such that $\sigma \left(w\right)=v_{i+1}$. Observe that $w\notin N\left(v_i\right)$ and $B\left[w\right]\cong B\left[v_i\right]$ and then $v_i{v}_{i+1}$ satisfies (iv).

We may assume that $\sigma \left(v_i\right)=u_j$. Then $j=2s$ and $\sigma \left(v_k\right)=v_{i-k}$, $k=1,\dots ,i-s$, $\sigma \left(v_{i-s+l}\right)=u_{s+l}$, $l=1,\dots ,j$. Observe that every vertex outside $(r,v_i)$-path and outside $(r,u_j)$-path points a branch in the new $d$-nary tree $(V,(E\setminus A)\cup B)$ isomorphic to a branch pointed in $T_d$. Since the family of branches in $T_d$ pointed by all vertices is the same as the family of branches in the new $d$-nary tree $(V,(E\setminus A)\cup B)$ pointed by all vertices, we have that the family of branches pointed by vertices $r,v_1,\dots ,v_s,v_{s+1},\dots ,v_i,u_{s+1},\dots ,u_j$ in $T_d$ is the same as the family of branches pointed by vertices $r,v_1,\dots ,v_s,v_{s+1},\dots ,v_i,u_{s+1},\dots ,u_j$ in the new $d$-nary tree $(V,(E\setminus A)\cup B)$. Moreover, we have that the family of branches pointed by vertices $u_{s+1},\dots ,u_j$ in $T_d$ is the same as family of branches pointed by vertices $r,\dots ,v_{s-1}$ in the new $d$-nary tree $(V,(E\setminus A)\cup B)$. Since $B\left[u_{k+1}\right]$ is a subgraph of $B\left[u_k\right]$, $k=s+1,\dots ,j-1$, in $T_d$, we obtain that $(u_{s+1},u_j)$-path according to $u_{j+1}$ and $(v_{s-1},r)$-path according to $v_s$ are twins. Then $(r,u_j)$-path according to $u_{j+1}$ and $(v_i,r)$-path according to $v_{i+1}$ are twins. Hence $i=2s$ and hence $(r,v_i)$-path is symmetric according to $v_{i+1}$ and $v_i{v}_{i+1}$ satisfies (i).

III. $B=\{r{v}_{i+1},v_i{u}_{j+1}\}$.

Then $\sigma \left(r\right)=u_j$. If $\sigma \left(v_i\right)\notin \{r,v_i\}$ then $\sigma \left(v_{i+1}\right)\ne v_{i+1}$ and hence $v_{i+1}\notin N\left(\sigma \left(v_i\right)\right)$. Therefore there is a vertex $w$ such that $\sigma \left(w\right)=v_{i+1}$ and $w\notin N\left(v_i\right)$, $B\left[w\right]\cong B\left[v_{i+1}\right]$. Then $v_i{v}_{i+1}$ satisfies (iv). If $\sigma \left(v_i\right)=v_i$, then $\sigma \left(v_{i-1}\right)=v_{i-1}$ and $\sigma \left(v_{i+1}\right)\in \left\{u_{j+1}\right\}\cup N\left(v_i\right)\setminus \{v_{i-1},v_{i+1}\}$. Hence $B\left[u_{j+1}\right]\cong B\left[v_{i+1}\right]$ and $v_i{v}_{i+1}$ satisfies (iv). We may assume that $\sigma \left(v_i\right)=r$. Then $(r,v_i)$-path according to $v_{i+1}$, $(u_j,r)$-path according to $u_{j+1}$ are twins and hence $i=j$. Moreover, vertices of $(r,v_i)$-path are mapped, in proper order, to vertices of $(u_j,r)$-path. Observe that every vertex outside $(r,v_i)$-path and outside of $(r,u_j)$-paths points a branch in the new $d$-nary tree $(V,(E\setminus A)\cup B)$ isomorphic to a branch pointed by it in $T_d$. Since the family of branches in $T_d$ pointed by all vertices is the same as the family of branches in the new $d$-nary tree $(V,(E\setminus A)\cup B)$ pointed by all vertices, we have that the family of branches pointed by vertices $r,v_1,\dots ,v_i,u_{s+1},\dots ,u_j$ in $T_d$ is the same as the family of branches pointed by vertices $r,v_1,\dots ,v_i,u_{s+1},\dots ,u_j$ in the new $d$-nary tree $(V,(E\setminus A)\cup B)$. Since vertices of $(r,v_i)$-path are mapped to vertices of $(u_j,r)$-path, we obtain that the family of branches in $T_d$ pointed by vertices $u_{s+1},\dots ,u_j$ and the family of branches in the new $d$-nary tree $(V,(E\setminus A)\cup B)$ pointed by vertices $v_{s+1},\dots ,v_i$ are the same. Moreover, $B\left[u_{k+1}\right]$ is a subgraph of $B\left[u_k\right]$ for $k=s+1,\dots ,j-1$ in $T_d$. Hence we obtain that $(v_{s+1},v_i)$-path according to $v_{i+1}$ and $(u_{s+1},u_j)$-path according to $u_{j+1}$ are twins. Then $v_i{v}_{i+1}$ satisfies (v).

Subcase 2.8. $A=\{v_i{v}_{i+1},r{w}_1\}$, $i\ge 1$, $(r,v_1,\dots ,v_i,v_{i+1})$ is $(r,v_{i+1})$-path.

Then $B=\{r{v}_{i+1},v_i{w}_1\}$ and $\sigma \left(r\right)=r$. It is easy to see that $B\left[v_{i+1}\right]$ is a nonisomorphic subgraph of $B\left[v_1\right]$. Hence without loss of generality we may assume that $\sigma \left(w_1\right)=v_{i+1}$, $\sigma \left(v_{i+1}\right)=w_1$. Then $B\left[w_1\right]\cong B\left[v_{i+1}\right]$ and $v_i{v}_{i+1}$ satisfies (iv).

Subcase 2.9. $A=\{v_i{v}_{i+1},w_j{w}_{j+1}\}$, $i\ge 1$, $j\ge 1$, $w_j{w}_{j+1}\notin E\left(B\left[v_1\right]\right)$, $(r,v_1,\dots ,v_i,v_{i+1})$ is $(r,v_{i+1})$-path, $(r,w_1,\dots ,w_j,w_{j+1})$ is $(r,w_{j+1})$-path.

We have several possibilities of choosing $B$.

I. $B=\{v_i{w}_{j+1},w_j{v}_{i+1}\}$.

We repeat the arguments of Subcase 2.7.I., replacing $u_j$ by $w_j$ and $u_{j+1}$ by $w_{j+1}$.

II. $B=\{r{w}_{j+1},v_{i+1}{w}_j\}$.

Then $\sigma \left(r\right)=v_i$. Since $\sigma \left(v_i\right)\ne v_i$, we have that $\sigma \left(v_{i+1}\right)\notin (N\left(v_i\right)\setminus \left\{v_{i+1}\right\})$. Observe that $\sigma \left(v_{i+1}\right)$ is not a vertex of $(v_i,r)$-path and is not a vertex of $(r,w_j)$-path because otherwise the branch pointed by $v_{i+1}$ is a nonisomorphic subgraph of the branch pointed by $\sigma \left(v_{i+1}\right)$ in the new $d$-nary tree $(V,(E\setminus A)\cup B)$, which is impossible. Hence $\sigma \left(v_i\right)$ is not a vertex of $(v_i,v_1)$-path and $(w_1,w_{j-1})$-path. Since $j\ge 1$, it is impossible that $\sigma \left(v_i\right)=w_j$. Hence $\sigma \left(v_{i+1}\right)\ne v_{i+1}$ and $v_i{v}_{i+1}$ satisfies (iv).

III. $B=\{r{v}_{i+1},v_i{w}_{j+1}\}$.

Then $\sigma \left(r\right)=w_j$. If $\sigma \left(v_i\right)\ne r$ then $\sigma \left(v_{i+1}\right)\ne v_{i+1}$ and hence $v_{i+1}\notin N\left(\sigma \left(v_i\right)\right)$. Hence there is a vertex $w$ such that $\sigma \left(w\right)=v_{i+1}$, and hence $w\notin N\left(v_i\right)$, $B\left[w\right]\cong B\left[v_{i+1}\right]$. Then we obtain that $v_i{v}_{i+1}$ satisfies (iv). Let us suppose that $\sigma \left(v_i\right)=r$. Then $(r,v_i)$-path according to $v_{i+1}$, $(w_j,r)$-path according to $w_{j+1}$ are twins and the branch pointed by $r$ in the new $d$-nary tree $(V,(E\setminus A)\cup B)$ is isomorphic to $B\left[v_i\right]$. Observe that it follows that $T_{w_j}\left[r\right]\cong B\left[v_i\right]$. But $B\left[v_i\right]$ is a nonisomorphic subgraph of $T_{w_j}\left[r\right]$, a contradiction.

Notes

Peer review under responsibility of Kalasalingam University.