Graceful Labeling of Posets

The concept of graph labeling was introduced in the mid-1960s by Rosa. In this paper, we introduce a notion of graceful labeling of a finite poset. We obtain graceful labeling of some postes such as a chain, a fence, and a crown. In 2002 Thakare, Pawar, and Waphare introduced the `adjunct' operation of two lattices with respect to an adjunct pair of elements. We obtain the graceful labeling of an adjunct sum of two chains with respect to an adjunct pair (0, 1).

AMS Subject Classification 2020: 06A05, 06A06, 05C78

Introduction

A graph labeling assigns integers to the vertices or edges (or both), subject to certain conditions. Interest in graph labeling began in the mid-1960s with the conjecture by Kotzing - Ringel [1] and a paper by Rosa [2]. There are different types of graph labeling such as prime labeling, magic labeling, antimagic labeling, graceful labeling [3], etc. Labeled graphs have wide applications in different fields such as circuit design, traffic control systems, communication network addressing, Automated Teller Machine (ATM) controlling devices, Local Area Network (LAN) network, radio astronomy, and Multiprotocol Label Switching (MPLS) protocols see [4-7]. In this paper, we define graceful labeling of finite posets. We obtain in particular graceful labeling of some posets like a chain, a fence, and a crown. Thakare, Pawar, and Waphare [8] introduced the `adjunct' operation of two lattices with respect to a pair of elements. In this connection, We obtain the graceful labeling of an adjunct sum of two chains concerning an adjunct pair (0, 1).

A non-empty set P, together with a binary relation £ that is reflexive, antisymmetric, and transitive is called a partially ordered set or a Poset. A Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set. Specifically, for a poset (P, £) each element of P represents a vertex in the plane, and whenever y covers x, it indicates that x £ y and there is no z such that x < z < y, which is represented by $x\prec y$ . These curves (or lines) may cross each other but must not touch any vertex other than endpoints; we call such curves (or lines) as edges. Two elements a, b Î P are said to be comparable if either a£b or b£a; otherwise they are said to be incomparable. A poset in which every pair of elements is comparable is called a chain. A chain on n elements is denoted by C_n. In particular, see Figure 1 for C₃.

Figure 1: For C3. A chain on n elements is denoted by Cn. In particular.

Definition 1 [9] A partially ordered set $F_n\mathrm{<mo>=</mo><mo>\{</mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_n\mathrm{<mo>\}</mo>}$  is called a fence (of order n ³ 3), if either $x_1\mathrm{<mo><</mo>}{x}_2$ , $x_2\mathrm{<mo>></mo>}{x}_3$ , , $x_{2m-1}\mathrm{<mo><</mo>}{x}_{2m}$ , $x_{2m}\mathrm{<mo>></mo>}{x}_{2m+1}$ , , $x_{n-1}\mathrm{<mo><</mo>}{x}_n$ , if n is even ( $x_{n-1}\mathrm{<mo>></mo>}{x}_n$  if n is odd) or $x_1\mathrm{<mo>></mo>}{x}_2$ , $x_2\mathrm{<mo><</mo>}{x}_3$ , , $x_{2m-1}\mathrm{<mo>></mo>}{x}_{2m}$ , $x_{2m}\mathrm{<mo><</mo>}{x}_{2m+1}$ , , $x_{n-1}\mathrm{<mo>></mo>}{x}_n$ , if n is even ( $x_{n-1}\mathrm{<mo><</mo>}{x}_n$  if n is odd) are the only comparability relations. A fence Fn is called a lower fence if $x_1\mathrm{<mo><</mo>}{x}_2$ , and upper fence if $x_1\mathrm{<mo>></mo>}{x}_2$ . In particular, see Figure 1 for F₃ and F₄.

 Definition 2 [10] A crown is a poset $\mathrm{<mo>\{</mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_n\mathrm{,}{y}_1\mathrm{,}{y}_2\mathrm{,}\dots \mathrm{,}{y}_n\mathrm{<mo>\}</mo>}$  of order $n\ge 2$ , whose elements satisfy precisely the comparabilities $x_1\mathrm{<mo><</mo>}{y}_1$ , $y_1\mathrm{<mo>></mo>}{x}_2$ , $x_2\mathrm{<mo><</mo>}{y}_2$ , $y_2\mathrm{<mo>></mo>}{x}_3$ , $x_3\mathrm{<mo><</mo>}{y}_3$ , $y_3\mathrm{<mo>></mo>}{x}_4$ , , $x_{n-1}\mathrm{<mo><</mo>}{y}_{n-1}$ , $y_{n-1}\mathrm{<mo>></mo>}{x}_n$ , $x_n\mathrm{<mo><</mo>}{y}_n$ , $y_n\mathrm{<mo>></mo>}{x}_1$ . The crown of order n is denoted by ${ℂ}_n$ . In particular, see Figure 1 for ${ℂ}_n$ .

For other definitions, notation, and terminology, see [11-13]. In the following section, we introduce the notion of graceful labeling of a poset.

2. Graceful labeling of posets

On the line of graceful labeling of graphs, we define graceful labeling of a finite poset as follows.

Definition 3 Let P be a poset on n elements with m coverings, $x_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_n$ . Let V = $\mathrm{<mo>\{</mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_n\mathrm{<mo>\}</mo>}$ and E = $\mathrm{<mo>\{</mo>0,1,2,3,}\dots \mathrm{,}m\mathrm{<mo>\}</mo>}$ . If $\varphi \mathrm{<mo>:</mo>}V\to E$  is a one-to-one function, then when each covering, say $x_i\prec x_j$ , is given the label $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_j\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ , the resulting cover labels are unique numbers from the set E. This is known as the graceful labeling of P. A poset is called graceful if it has a graceful labeling. For example, C₃, F₄ and ${ℂ}_4$  are graceful (Figure 2).

Figure 2: A poset is called graceful if it has a graceful labeling.

Theorem 2.1 A chain Cn is graceful for $n\ge 2$ .

Proof. Let $C_n\mathrm{<mo>:</mo>}{x}_1\prec x_2\prec \cdots \prec x_n$  be a chain. Note that C_n contains n - 1 edges. Let V = $\mathrm{<mo>\{</mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_n\mathrm{<mo>\}</mo>}$  be the set of elements of C_n and E = {0, 1, 2, …, n-1}. Define a map $\varphi \mathrm{<mo>:</mo>}V\to E$  as follows.

$\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\{\begin{array}{cc}\frac{i-1}{2}\mathrm{,}& \text{if i is odd}\\ n-\frac{i}{2}\mathrm{,}& \text{if i is even}\mathrm{.}\end{array}$

We claim that the map φ is the required graceful labeling of C_n. Firstly we prove that φ is one - one. One of the following four cases occurs.

1. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_j\mathrm{<mo\; stretchy="false">)</mo>}$  and both i and j are odd. But then $\frac{i-1}{2}\mathrm{<mo>=</mo>}\frac{j-1}{2}\mathfrak{A}$  which implies that i = j and hence $x_i\mathrm{<mo>=</mo>}{x}_j$ .
2. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_j\mathrm{<mo\; stretchy="false">)</mo>}$  and both i and j are even. But then $n-\frac{i}{2}\mathrm{<mo>=</mo>}n-\frac{j}{2}$  implies that i = j and hence $x_i\mathrm{<mo>=</mo>}{x}_j$ .
3. i is odd and j is even. Then i $\ne$  j and $x_i\ne x_j\Rightarrow \varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . For if, suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_j\mathrm{<mo\; stretchy="false">)</mo>}\Rightarrow \frac{i-1}{2}\mathrm{<mo>=</mo>}n-\frac{j}{2}$ $\Rightarrow$ $i-\mathrm{1<mo>=</mo>2}n-j\Rightarrow i+j\mathrm{<mo>=</mo>2}n+1$ . This is not possible, since $1\le i\le n$  and $1\le j\le n$ .
4. i is even and j is odd. In this case, we get the proof on similar lines of Case (3). Thus, φis one - one.

Secondly, we prove that the edge labels of C_n are all distinct. Now the edge label between the elements xi and xi+1 is given by $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_{i+1}\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ .

Suppose for $i\ne j$ , $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_{i+1}\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_{j+1}\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_j\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ . One of the following three cases occurs.

1. Both i and j are odd. Then we have $\mathrm{<mo>|</mo>}n-\mathrm{<mo\; stretchy="false">(</mo>}\frac{i+1}{2}\mathrm{<mo\; stretchy="false">)</mo>}-\mathrm{<mo\; stretchy="false">(</mo>}\frac{i-1}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}n-\mathrm{<mo\; stretchy="false">(</mo>}\frac{j+1}{2}\mathrm{<mo\; stretchy="false">)</mo>}-\mathrm{<mo\; stretchy="false">(</mo>}\frac{j-1}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ . This implies that $\mathrm{<mo>|</mo>}n-i\mathrm{<mo>|</mo><mo>=</mo><mo>|</mo>}n-j\mathrm{<mo>|</mo>}$  and hence i = j, which is a contradiction.
2. Both i and j are even. Then we have $\mathrm{<mo>|</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i+\mathrm{1<mo\; stretchy="false">)</mo>}-1}{2}-\mathrm{<mo\; stretchy="false">(</mo>}n-\frac{i}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}-1}{2}-\mathrm{<mo\; stretchy="false">(</mo>}n-\frac{j}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ . This implies that $\mathrm{<mo>|</mo>}n-i\mathrm{<mo>|</mo><mo>=</mo><mo>|</mo>}n-j\mathrm{<mo>|</mo>}$  and hence i = j which is a contradiction.
3. Without loss of generality, if i is even and j is odd, then we have $\mathrm{<mo>|</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i+\mathrm{1<mo\; stretchy="false">)</mo>}-1}{2}-\mathrm{<mo\; stretchy="false">(</mo>}n-\frac{i}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}n-\frac{\mathrm{<mo\; stretchy="false">(</mo>}j+\mathrm{1<mo\; stretchy="false">)</mo>}}{2}-\mathrm{<mo\; stretchy="false">(</mo>}\frac{j-1}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ . This implies that $\mathrm{<mo>|</mo>}i-n\mathrm{<mo>|</mo><mo>=</mo><mo>|</mo>}n-j\mathrm{<mo>|</mo>}$  and hence i = j, which is a contradiction. Hence the edge labels of Cn are distinct.

Therefore φ is required graceful labeling Cn.

Remark 1 Let $C_n\mathrm{<mo>:</mo>}{x}_0\prec x_1\prec \cdots \prec x_{n-1}$  be a chain where $n\ge 2$ . Define a function $\psi \mathrm{<mo>:</mo>}V\mathrm{<mo\; stretchy="false">(</mo>}{C}_n\mathrm{<mo\; stretchy="false">)</mo>}\to \mathrm{<mo>\{</mo>0,1,2,}\dots \mathrm{,}n-\mathrm{1<mo>\}</mo>}$  as follows.

1. If n is odd

$\psi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\{\begin{array}{cc}\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}-\frac{n-i}{2}\mathrm{,}& \text{if i is even}\\ \frac{n-i}{2}-\mathrm{1,}& \text{if i is odd}\mathrm{.}\end{array}$

2. If n is even

$\psi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\{\begin{array}{cc}\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo>}-\frac{n-i}{2}\mathrm{,}& \text{if i is odd}\\ \frac{n-i}{2}-\mathrm{1,}& \text{if i is even}\mathrm{.}\end{array}$

Then Y is also a graceful labeling of C_n.

By the arguments similar to one given in the proof of Theorem 2.1, we obtain the proof of the following result, since, F_n the edge labels are the same as that of the chain C_n.

Corollary 2.2 A fence Fn is graceful for n $\ge$  3.

Note that, the graceful labeling of a chain on n elements and a fence on n elements are the same. Therefore, we have the following.

Theorem 2.3 A crown ${ℂ}_n$ is graceful if n is even.

Proof. Suppose the set of elements of crown ${ℂ}_n$  is $\text{V }=\mathrm{<mo>\{</mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_n\mathrm{,}{y}_1\mathrm{,}{y}_2\mathrm{,}\dots \mathrm{,}{y}_n\mathrm{<mo>\}</mo>}$ with 2n coverings $x_1\prec y_1\mathrm{,}{x}_2\prec y_1\mathrm{,}{x}_2\prec y_2\mathrm{,}{x}_3\prec y_2\mathrm{,}\cdots \mathrm{,}{x}_{n-1}\prec y_{n-1}\mathrm{,}{x}_n\prec y_{n-1}\mathrm{,}{x}_n\prec y_n\mathrm{,}{x}_1\prec y_n$ . Let $\text{E }=\mathrm{<mo>\{</mo>0,1,2,}\dots \mathrm{,2}n\mathrm{<mo>\}</mo>}$ . Define a map $\varphi \mathrm{<mo>:</mo>}V\to E$ as follows.

$\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}i-1$ , if $1\le i\le n$ , and $\varphi (y_i)\text{ = }\{\begin{array}{l}2n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>,}if\text{ 1}\le i\le \frac{n}{2}.\\ 2n-i,if\frac{n}{2}+1\le i\le n.\end{array}$

We claim that the map f is a graceful labeling of ${ℂ}_n$ . Firstly we prove that f is one-one. One of the following five cases occurs.

1. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_j\mathrm{<mo\; stretchy="false">)</mo>}$  and $1\le i\mathrm{,}j\le n$ . Then i - 1 = j - 1 implies that i - j and hence xi = xj.
2. Suppose that $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_j\mathrm{<mo\; stretchy="false">)</mo>}$  and $1\le i\mathrm{,}j\le \frac{n}{2}$ . Then $2n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo>=</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}j-\mathrm{1<mo\; stretchy="false">)</mo>}$  implies that i - j and hence yi = yj.
3. that $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_j\mathrm{<mo\; stretchy="false">)</mo>}$  and $\frac{n}{2}+1\le i\mathrm{,}j\le n$ . Then 2n - i = 2n -j implies that i - j and hence yi = yj.
4. $1\le i\le \frac{n}{2}$  and $x_i\ne y_i$ . Then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo>}$ . For if, suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo>}$  implies that $i-\mathrm{1<mo>=</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}\Rightarrow 2i\mathrm{<mo>=</mo>2}n+2\Rightarrow i\mathrm{<mo>=</mo>}n+1$  which is not possible.
5. $\frac{n}{2}+1\le i\le n$  and $x_i\ne y_i$ . Then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo>}$ . Since, $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo>}$  then $i-\mathrm{1<mo>=</mo>2}n-i\Rightarrow 2i\mathrm{<mo>=</mo>2}n+1$ , which is not possible.

Thus φ is one - one.

Secondly, we prove the edge labels of ${ℂ}_n$ are all distinct. Consider the edge labels of ${ℂ}_n$ for $1\le i\le n$ as $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ , for $2\le i\le n$ as $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{i-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ , and $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ . One of the following five cases occurs.

$\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$

Suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_k\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_k\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}k-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}k-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}-2n+2i-\mathrm{2<mo>|</mo><mo>=</mo><mo>|</mo>}-2n+2k-\mathrm{2<mo>|</mo>}\Rightarrow i\mathrm{<mo>=</mo>}k$ which is a contradiction. Now let $\frac{n}{2}+1\le i\mathrm{,}k\le n$ and $i\ne k$ . Suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_k\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_k\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}k-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-k\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}-2n+2i-\mathrm{1<mo>|</mo><mo>=</mo><mo>|</mo>}-2n+2k-\mathrm{1<mo>|</mo>}\Rightarrow i\mathrm{<mo>=</mo>}k$ which is a contradiction.

2. $2\le i\mathrm{,}k\le \frac{n}{2}$ and $i\ne k$ .

Suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{i-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_k\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{k-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}k-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}k-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}-2n+2i-\mathrm{3<mo>|</mo><mo>=</mo><mo>|</mo>}-2n+2k-\mathrm{3<mo>|</mo>}\Rightarrow i\mathrm{<mo>=</mo>}k$ which is a contradiction. Now let $\frac{n}{2}+1\le i\mathrm{,}k\le n$ and $i\ne k$ . Suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{i-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_k\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{k-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}k-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}k-\mathrm{1<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}-2n+2i-\mathrm{2<mo>|</mo><mo>=</mo><mo>|</mo>}-2n+2k-\mathrm{2<mo>|</mo>}\Rightarrow i\mathrm{<mo>=</mo>}k$ which is a contradiction.

3. $1\le i\le \frac{n}{2}$ and suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>1}-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}n-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>2}i-2n-\mathrm{2<mo>|</mo><mo>=</mo><mo>|</mo>}-n+\mathrm{1<mo>|</mo>}\Rightarrow 2i\mathrm{<mo>=</mo>}n+3$ which is not possible. Let $\frac{n}{2}+1\le i\le n$ and suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}i\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>1}-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>2}i-2n-\mathrm{1<mo>|</mo><mo>=</mo><mo>|</mo>}-n\mathrm{<mo>|</mo>}\Rightarrow 2i-\mathrm{1<mo>=</mo>3}n$ which is not possible.

4. $2\le i\le \frac{n}{2}$ and suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{i-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>1}-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}n\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-2n+i-\mathrm{2<mo>|</mo><mo>=</mo><mo>|</mo>}-n\mathrm{<mo>|</mo>}\Rightarrow 2i-2n-\mathrm{3<mo>=</mo>}n\Rightarrow 2i-\mathrm{3<mo>=</mo>3}n$ which is not possible. Let $\frac{n}{2}+1\le i\le n$ and suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{i-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>1}-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>2}i-2n-\mathrm{2<mo>|</mo><mo>=</mo><mo>|</mo>}-n\mathrm{<mo>|</mo>}\Rightarrow 2i-\mathrm{2<mo>=</mo>3}n$ which is not possible.

5. $1\le i\le \frac{n}{2}$ and $2\le k\le \frac{n}{2}$ , suppose $\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_i\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_i\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_k\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{k-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>}i-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}k-1-\mathrm{<mo\; stretchy="false">(</mo>2}n-\mathrm{<mo\; stretchy="false">(</mo><mo\; stretchy="false">(</mo>}k-\mathrm{1<mo\; stretchy="false">)</mo>}-\mathrm{1<mo\; stretchy="false">)</mo><mo>|</mo>}\Rightarrow \mathrm{<mo>|</mo>2}i-2n-\mathrm{2<mo>|</mo><mo>=</mo><mo>|</mo>2}k-2n-\mathrm{3<mo>|</mo>}\Rightarrow 2i-\mathrm{2<mo>=</mo>2}k-3\Rightarrow 2i-2k\mathrm{<mo>=</mo>}-1\Rightarrow i-k\mathrm{<mo>=</mo>}\frac{-1}{2}$ which is not possible.

Here, the map φ gives the required graceful labeling of the ${ℂ}_n$ .

Proof. Let ${ℂ}_n$ be crown with the set of elements $V\mathrm{<mo>=</mo><mo>\{</mo>}{x}_1\mathrm{,}{x}_2\mathrm{,}\dots \mathrm{,}{x}_n\mathrm{,}{y}_1\mathrm{,}{y}_2\mathrm{,}\dots \mathrm{,}{y}_n\mathrm{<mo>\}</mo>}$ with 2n Coverings $x_1\prec y_1\mathrm{,}{x}_2\prec y_1\mathrm{,}{x}_2\prec y_2\mathrm{,}{x}_3\prec y_2\mathrm{,}\cdots \mathrm{,}{x}_{n-1}\prec y_{n-1}\mathrm{,}{x}_n\prec y_{n-1}\mathrm{,}{x}_n\prec y_n\mathrm{,}{x}_1\prec y_n$ . Let $E\mathrm{<mo>=</mo><mo>\{</mo>0,1,2,}\dots \mathrm{,2}n\mathrm{<mo>\}</mo>}$ . Suppose ${ℂ}_n$ has p - labeling as $\varphi \mathrm{<mo>:</mo>}V\to E$ . Taking the sum of edge labels of the crown ${ℂ}_n$ . We have $0\le \mathrm{<mo\; stretchy="false">(</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\dots +\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_{n-1}\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{n-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_n\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{n-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_n\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo\; stretchy="false">)</mo>}$ $\le \mathrm{<mo\; stretchy="false">(</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\dots +\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_{n-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{n-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{n-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo\; stretchy="false">)</mo>}$ = $\mathrm{2<mo\; stretchy="false">(</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\dots +\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\dots +\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}$ ).

Therefore,

$\mathrm{<mo\; stretchy="false">(</mo><mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_2\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\dots +\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_{n-1}\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{n-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_n\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_{n-1}\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_n\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{x}_1\mathrm{<mo\; stretchy="false">)</mo>}-\varphi \mathrm{<mo\; stretchy="false">(</mo>}{y}_n\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo\; stretchy="false">)</mo>}\equiv \mathrm{0<mo\; stretchy="false">(</mo>}$ mod 2)

In the crown ${ℂ}_n$ , edge labels are from 1 to 2n. So, the sum of edge labels of ${ℂ}_n$ is

${\displaystyle {\sum }_{k\mathrm{<mo>=</mo>1}}^{2k}}k\mathrm{<mo>=</mo>}\frac{2n\mathrm{<mo\; stretchy="false">(</mo>2}n+\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo>=</mo>}n\mathrm{<mo\; stretchy="false">(</mo>2}n+\mathrm{1<mo\; stretchy="false">)</mo>}$ which is odd. As n is odd, 2n+1 is odd, and therefore n(2n+1) must be odd. Therefore we get a contradiction. Hence we conclude that ${ℂ}_n$ has no graceful labeling, if n odd.

3. Adjunct sum of lattices

In 2002, Thakare, Pawar, and Waphare [8] introduced the concept of an adjunct sum of lattices.

Definition 4 [8] Suppose L1 and L2 are two disjoint lattices and (a,b) is a pair of elements in L1 such that a<b and $a\cancel{\prec }b$ . Define the partial order $\le$  on $L\mathrm{<mo>=</mo>}{L}_1\cup L_2$  with respect to the pair (a,b) as follows: $x\le y$  in L if $x\mathrm{,}y\in L_1$  and $x\le y$  in L1, or $x\mathrm{,}y\in L_2$  and $x\le y$  in $L_2$ , or $x\in L_1\mathrm{,}$ $y\in L_2$  and $x\le a$  in L1, or $x\in L_2\mathrm{,}$ $y\in L_1$  and $b\le y$  in L1.

It is easy to see that L is a lattice containing L₁ and L₂ as sublattices. The procedure for obtaining L in this way is called adjunct operation (or adjunct sum) of L₁ with L₂. We call the pair (a,b) as an adjunct pair and L as an adjunct of L₁ with L₂ concerning the adjunct pair (a,b) and write $L\mathrm{<mo>=</mo>}{L}_1{\mathrm{<mo\; stretchy="false">]</mo>}}_a^b{L}_2$ . A diagram of L is obtained by placing a diagram of L₁ and a diagram of L₂ side by side in such a way that the largest element 1 of L₂ is at lower position than b and the least element 0 of L₂ is at the higher position than a and then by adding the coverings <1, b> and <a, 0>, as shown in Figure III. This gives $\mathrm{<mo>|</mo>}E\mathrm{<mo\; stretchy="false">(</mo>}L\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo><mo>=</mo><mo>|</mo>}E\mathrm{<mo\; stretchy="false">(</mo>}{L}_1\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+\mathrm{<mo>|</mo>}E\mathrm{<mo\; stretchy="false">(</mo>}{L}_2\mathrm{<mo\; stretchy="false">)</mo><mo>|</mo>}+2$ .

Figure 3: A diagram of L is obtained by placing a diagram of L1 and a diagram of L2.

The adjunct sum is often utilized to construct and analyze complex lattices from simpler, well-defined components while retaining the essential properties of a lattice. To obtain graceful labeling for lattices formed by the adjunct sum of two chains, we construct the following sets. Let A = $\mathrm{<mo>\{</mo>1,3,5,}\dots \mathrm{,}m-\mathrm{1<mo>\}</mo>,}m\ge 3$ , $B^{\prime }\mathrm{<mo>=</mo><mo>\{</mo>2,4,6,}\dots \mathrm{,}\frac{m+n+1}{2}\mathrm{<mo>\}</mo>,}{B^{\prime }}^{\prime }\mathrm{<mo>=</mo><mo>\{</mo>}\frac{m+n+1}{2}+\mathrm{2,}\frac{m+n+1}{2}+\mathrm{4,}\dots \mathrm{,}m\mathrm{<mo>\}</mo>}$ and $B\mathrm{<mo>=</mo>}{B}^{\prime }\cup {B^{\prime }}^{\prime }$ . Also, let $D\mathrm{<mo>=</mo><mo>\{</mo>1,3,5,}\dots \mathrm{,}n\mathrm{<mo>\}</mo>,}n\ge \mathrm{1,}{F}^{\prime }\mathrm{<mo>=</mo><mo>\{</mo>2,4,6,}\dots \mathrm{,}\frac{m+n+1}{2}-\mathrm{2<mo>\}</mo>,}{F^{\prime }}^{\prime }\mathrm{<mo>=</mo><mo>\{</mo>}\frac{m+n+1}{2}\mathrm{,}\frac{m+n+1}{2}+\mathrm{2,}\dots \mathrm{,}n-\mathrm{1<mo>\}</mo>}$ , and $F\mathrm{<mo>=</mo>}{F}^{\prime }\cup {F^{\prime }}^{\prime }$ .

Theorem 3.1 Let C and C¢ be the chains with $\mathrm{<mo>|</mo>}C\mathrm{<mo>|</mo><mo>=</mo>}m\ge$  3, $\mathrm{<mo>|</mo>}{C}^{\prime }\mathrm{<mo>|</mo><mo>=</mo>}n\ge 1$  and $L\mathrm{<mo>=</mo>}C{\mathrm{<mo\; stretchy="false">]</mo>}}_0^1{C}^{\prime }$ . Then L has graceful labeling if m º 2(mod 4) and n º 1(mod 4).

Proof. Let C and $C^{\prime }$  be the chains with m and n elements, respectively. Suppose m º 2(mod 4) and n º 1(mod 4) and. Suppose $C\mathrm{<mo>=</mo>}{a}_1\prec a_2\prec a_3\dots \prec a_m$ , $C^{\prime }\mathrm{<mo>=</mo>}{b}_1\prec b_2\prec b_3\dots \prec b_n$  and $L\mathrm{<mo>=</mo>}C{\mathrm{<mo\; stretchy="false">]</mo>}}_0^1{C}^{\prime }$ . Clearly, L has m+n elements and m+n coverings (edges). Suppose V = $\mathrm{<mo>\{</mo>}{a}_1\mathrm{,}{a}_2\mathrm{,}{a}_3\mathrm{,}\dots \mathrm{,}{a}_m\mathrm{,}{b}_1\mathrm{,}{b}_2\mathrm{,}{b}_3\mathrm{,}\dots \mathrm{,}{b}_n\mathrm{<mo>\}</mo>}$  and E = {0, 1, 2, … , m+n} . Consider a map $\varphi \mathrm{<mo>:</mo>}V\to E$  defined as follows :

$\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\{\begin{array}{cc}\frac{i-1}{2}& \text{if}i\in A\\ m+n-\lfloor \frac{i-1}{2}\rfloor & \text{if}i\in B^{\prime }\\ m+n-\frac{i}{2}& \text{if}i\in {B^{\prime }}^{\prime }\end{array}$

$\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\{\begin{array}{cc}\frac{m+n-j}{2}& \text{if}j\in D\\ \frac{m+n+j-1}{2}& \text{if}j\in F^{\prime }\\ \frac{m+n+j+1}{2}& \text{if}j\in {F^{\prime }}^{\prime }\end{array}$

We claim that the map f is the required graceful labeling for lattice L. Firstly we prove that f is one - one. For this purpose, we consider the following sets. Let $S_1\mathrm{<mo>=</mo><mo>\{</mo>}{a}_i\mathrm{<mo>|</mo>}i\in A\mathrm{<mo>\}</mo>}$ ${S^{\prime }}_2\mathrm{<mo>=</mo><mo>\{</mo>}{a}_i\mathrm{<mo>|</mo>}i\in B^{\prime }\mathrm{<mo>\}</mo>}$ , ${{S^{\prime }}^{\prime }}_2\mathrm{<mo>=</mo><mo>\{</mo>}{a}_i\mathrm{<mo>|</mo>}i\in {B^{\prime }}^{\prime }\mathrm{<mo>\}</mo>}$ , and $S_2\mathrm{<mo>=</mo>}{S^{\prime }}_2\cup {{S^{\prime }}^{\prime }}_2$ . Also, let $T_1\mathrm{<mo>=</mo><mo>\{</mo>}{b}_j\mathrm{<mo>|</mo>}j\in D\mathrm{<mo>\}</mo>,}{T^{\prime }}_2\mathrm{<mo>=</mo><mo>\{</mo>}{b}_j\mathrm{<mo>|</mo>}j\in F\mathrm{<mo>\}</mo>}$ , ${{T^{\prime }}^{\prime }}_2\mathrm{<mo>=</mo><mo>\{</mo>}{b}_j\mathrm{<mo>|</mo>}j\in {F^{\prime }}^{\prime }\mathrm{<mo>\}</mo>}$  and $T_2\mathrm{<mo>=</mo>}{T^{\prime }}_1\cup {{T^{\prime }}^{\prime }}_2$ . Let a, b Î V. Now to show f is one-one. For this proof, one of the following five cases occurs depending on a, b Î Sk (k = 1, 2) and a, b ÎTk (k =1, 2):

1) Suppose a, b ∈ S_k (k = 1, 2).

a) Suppose a, b ∈ S₁. Therefore a = ai and b = aj for i, j ∈ A. Consider $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . $\Rightarrow \frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo>=</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}j-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}$ for i, j ∈ A. $\Rightarrow i\mathrm{<mo>=</mo>}j$ $\Rightarrow a_i\mathrm{<mo>=</mo>}{a}_j$ i.e a = b.

b) Let a, b ∈ S₂ , here we have three parts.

1. Suppose a, b Î S¢2. Therefore a = ai and b = a_j for $i\mathrm{,}j\in B^{\prime }$ . Consider $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j$ ).  for $i\mathrm{,}j\in B^{\prime }$ . $\Rightarrow \frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo>=</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}j-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}$ $\Rightarrow i\mathrm{<mo>=</mo>}j\Rightarrow a_i\mathrm{<mo>=</mo>}{a}_j$  i.e. a = b.
2. Suppose a, b ∈ S¢¢2. Therefore a = a_i and b = a_j for $i\mathrm{,}j\in {B^{\prime }}^{\prime }$ . Consider $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . $m+n-\frac{i}{2}\mathrm{<mo>=</mo>}m+n-\frac{j}{2}$ $\Rightarrow i\mathrm{<mo>=</mo>}j\Rightarrow a_i\mathrm{<mo>=</mo>}{a}_j$  i.e. a = b.
3. Without loss of generality suppose that a ∈ S¢₂ and b ∈ S¢¢2. Therefore a = a_i and b = a_j for $i\in B^{\prime }$  and j ∈ B¢¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . Therefore $m+n-\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo>=</mo>}m+n-\frac{j}{2}$ . $\Rightarrow \frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo>=</mo>}\frac{j}{2}$ . Which is not possible, since $\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo><</mo>}\frac{j}{2}$  for $i\in B^{\prime }$  and $j\in {B^{\prime }}^{\prime }$ . Thus, $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .

c) Without loss of generality suppose that a ∈ S₁ and b ∈ S′₂, then we have the following two cases.

1. Let a ∈ S₁ and b ∈ S¢₂. Therefore a = ai and b = aj for i ∈ A and jÎB¢. Claim: $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . Therefore $\frac{i-1}{2}\mathrm{<mo>=</mo>}m+n-\frac{j-1}{2}$ . i.e. $m+n\mathrm{<mo>=</mo>}\frac{i-1}{2}+\frac{j-1}{2}$ . Which is not possible, since $m+n\mathrm{<mo>></mo>}\frac{i-1}{2}+\frac{j-1}{2}$ , as $i\le m-1$ and $j\le \frac{m+n+1}{2}$ . Thus, $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .
2. Let a ∈ S₁ and b ∈S¢¢₂. Therefore a = a_i and b = a_j for i ∈ A and j∈B¢¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$  For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j$ ). Therefore $\frac{i-1}{2}\mathrm{<mo>=</mo>}m+n-\frac{j}{2}$ . i.e. $i+j-\mathrm{1<mo>=</mo>2<mo\; stretchy="false">(</mo>}m+n\mathrm{<mo\; stretchy="false">)</mo>.}$  Which is not possible since, $\mathrm{2<mo\; stretchy="false">(</mo>}m+n\mathrm{<mo\; stretchy="false">)</mo><mo>></mo>}i+j-1$  as $i\le m-\mathrm{1,}j\le n$ . Thus, $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .

2. Suppose a,b ∈ T_k (k = 1, 2.)

a) Suppose a,b ∈ T₁. Therefore a = b_i and b = b_j for i, j ∈ D. Suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . Therefore $\frac{m+n-i}{2}\mathrm{<mo>=</mo>}\frac{m+n-j}{2}$ . $\Rightarrow i\mathrm{<mo>=</mo>}j\Rightarrow b_i\mathrm{<mo>=</mo>}{b}_j$ i.e. a = b.

b) Suppose a,b ∈ T₂, here we have three parts.

1. Suppose a,b ∈ T¢2. Therefore a = b_i and b = b_j for i, j ∈ F¢. Consider $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . $\Rightarrow \frac{m+n+i-1}{2}\mathrm{<mo>=</mo>}\frac{m+n+j-1}{2}$ . $\Rightarrow i\mathrm{<mo>=</mo>}j\Rightarrow b_i\mathrm{<mo>=</mo>}{b}_j$  i.e. a = b.
2. Suppose a,b ∈ T¢¢₂. Therefore a = b_i and b = b_j for i, j ∈ F¢¢. Suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . $\Rightarrow \frac{m+n+i+1}{2}\mathrm{<mo>=</mo>}\frac{m+n+j+1}{2}$ $\Rightarrow i\mathrm{<mo>=</mo>}j\Rightarrow b_i\mathrm{<mo>=</mo>}{b}_j$  i.e. a = b.
3. Without loss of generality a ∈ T¢₂ and b ∈ T¢¢₂. Therefore a = bi and b = b_j for some i ∈ F¢ and j ∈ F¢¢. Claim: $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$  For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . Therefore $\frac{m+n+i-1}{2}\mathrm{<mo>=</mo>}\frac{m+n+j+1}{2}$ . i.e. $i-\mathrm{1<mo>=</mo>}j+1\Rightarrow i\mathrm{<mo>=</mo>}j+2$ . Which is not possible since j > i as $i\le \frac{m+n+1}{2}-2$ , $j\le n-1$ . $\Rightarrow \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .

c) Without loss of generality, let a ∈ T₁ and b ∈ T₂, then we have the following two parts.

1. Suppose a ∈ T₁ and b ∈ T¢2. Therefore a = b_i and b = b_j for some i ∈ D and j ∈ F¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$  For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . $\Rightarrow \frac{m+n-i}{2}\mathrm{<mo>=</mo>}\frac{m+n+j-1}{2}$  which is not possible since i ∈ D and $j\in F^{\prime }$ . $\Rightarrow \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .
2. Suppose a ∈ T₁ and b ∈ T¢¢₂. Therefore a = b_i and b = b_j for some i ∈ D and j ∈ F¢¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . Therefore $\frac{m+n-i}{2}\mathrm{<mo>=</mo>}\frac{m+n+j+1}{2}$  i.e. $-i\mathrm{<mo>=</mo>}j+1$ , which is not possible since i ∈ D and $j\in {F^{\prime }}^{\prime }$ . $\Rightarrow \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .

3. Let a ∈ S_k (k = 1,2) and b ∈ T_k (k = 1, 2).

a) Suppose a ∈ S₁ and b ∈ T₁. Therefore a = a_i and b = b_j for some i ∈ A and j ∈ D. Claim: If $a\ne b$ then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . Therefore $\frac{i-1}{2}\mathrm{<mo>=</mo>}\frac{m+n-j}{2}$ . $\Rightarrow m+n\mathrm{<mo>=</mo>}i+j-1$ which is not possible since $m+n\mathrm{<mo>></mo>}i+j-1$ , since $i\le m-1$ , and $j\le n$ . Thus, $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .

b) Suppose a ∈ S₁ and b ∈ T₂, then we have the following two parts.

1. Suppose a ∈ S₁ and b ∈ T¢₂ and. Therefore a = a_i and b = b_j for i ∈ A and j ∈ F¢ . Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . $\Rightarrow \frac{i-1}{2}\mathrm{<mo>=</mo>}\frac{m+n+j-1}{2}$ . $\Rightarrow m+n\mathrm{<mo>=</mo>}i-j$  which is not possible since $m+n\mathrm{<mo>></mo>}i-j$ , since $i\le m-1$  and $j\le \frac{m+n1}{2}-2$ . Thus, $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .
2. Suppose a ∈ S₁ and b ∈ T¢¢₂. Therefore a = a_i and b = b_j. for i ∈ A and j ∈ F¢¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$  For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . $\Rightarrow \frac{i-1}{2}\mathrm{<mo>=</mo>}\frac{m+n+j+1}{2}$ $\Rightarrow m+n\mathrm{<mo>=</mo>}i-j$  which is not possible since $m+n\mathrm{<mo>></mo>}i-j-2$ , as $i\le m-1$  and $j\le n-1$ . $\Rightarrow \varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .

c) Suppose a ∈ S₂ and b ∈ T₂ and then we have the following parts.

1. Suppose a ∈ S¢₂ and b ∈ T¢₂. Therefore a = a_i and b = b_j for some i ∈ B¢ and j ∈ F¢ . Claim: If $a\ne b$ then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j$ ). Therefore $m+n-\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo>=</mo>}\frac{m+n+j-1}{2}$ . $\Rightarrow \mathrm{2<mo\; stretchy="false">(</mo>}m+n\mathrm{<mo\; stretchy="false">)</mo>}-\mathrm{2<mo\; stretchy="false">(</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}m+n+j-1$ . $\Rightarrow m+n\mathrm{<mo>=</mo>}j+\mathrm{2<mo\; stretchy="false">(</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo\; stretchy="false">)</mo>}-1$  which is not possible since, $m+n\mathrm{<mo>></mo>}j-\mathrm{<mo\; stretchy="false">(</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo\; stretchy="false">)</mo>}-1$  since, $i\le \frac{m+n+1}{2}$  and $j\le \frac{m+n+1}{2}$ . Thus $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .
2. Suppose a ∈ S¢₂ and b ∈ T¢¢₂. Therefore a = ai and b = bj for i ∈ B¢ and j ∈ F¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j$ ). $\Rightarrow m+n-\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo>=</mo>}\frac{m+n+j+1}{2}$ . $\Rightarrow \mathrm{2<mo\; stretchy="false">(</mo>}m+n\mathrm{<mo\; stretchy="false">)</mo>}-\mathrm{2<mo\; stretchy="false">(</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}m+n+j-1$ . $m+n\mathrm{<mo>=</mo>}j+\mathrm{2<mo\; stretchy="false">(</mo>}\frac{\mathrm{<mo\; stretchy="false">(</mo>}i-\mathrm{1<mo\; stretchy="false">)</mo>}}{2}\mathrm{<mo\; stretchy="false">)</mo>}+1$  which is not possible Since, $i\in B^{\prime }$  and $j\in F^{\prime }$ . $\Rightarrow \varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .
3. Suppose a ∈ S¢¢₂ and b ∈ T¢₂. Therefore a = ai and b = bj for i ∈ B¢¢ and j ∈ F¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$ . Therefore $m+n-\frac{i}{2}$  = $\frac{m+n+j-1}{2}$ . $\Rightarrow \mathrm{<mo\; stretchy="false">(</mo>}m+n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}j+i-1$  which is not possible since, $i\in {B^{\prime }}^{\prime }$  and $j\in F^{\prime }$ . Thus, $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ .
4. Suppose a ∈ S¢¢₂ and b ∈ T¢¢₂. Therefore a = ai and b = bj for i ∈ B¢¢ and j ∈F¢¢. Claim: If $a\ne b$  then $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Suppose $a\ne b$ . For, if suppose $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j$ .) Therefore $m+n-\frac{i}{2}\mathrm{<mo>=</mo>}\frac{m+n+j+1}{2}$ . $\Rightarrow \mathrm{<mo\; stretchy="false">(</mo>}m+n\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}j+i+1$  which is not possible since i ∈ B¢¢ and j ∈ F¢¢. $\Rightarrow \varphi \mathrm{<mo\; stretchy="false">(</mo>}{a}_i\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}{b}_j\mathrm{<mo\; stretchy="false">)</mo>}$  i.e. $\varphi \mathrm{<mo\; stretchy="false">(</mo>}a\mathrm{<mo\; stretchy="false">)</mo>}\ne \varphi \mathrm{<mo\; stretchy="false">(</mo>}b\mathrm{<mo\; stretchy="false">)</mo>}$ . Hence f is one - one function.