# Number of Labels used in reduction of Isomorphism of Labelled Graph to Graph Isomorphism

From "Lecture Notes in Computer Science" by Christoph M. Hoffmann ,

Assume that both $X$ and $X'$ have $n$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the vertices of $X$ and of $X'$. In time polynomial in the length of the input we can rename the labels and may assume, therefore, that $L = \{1 ..... k\}$ is the set of labels assigned by $\lambda$ and $\mu$. Note that $k\leq2n$ .We describe how to construct $Z$ from $(X,\lambda)$. The construction of $Z'$ is done in the same way. Let $X = (V,E), V = \{v_1..... v_n\}$. Intuitively, we obtain $Z$ from $X$ by attaching to each vertex $v_i$ a complete graph with $n + r$ vertices, where $\lambda (v_i) = r$. Note that $r\leq2n$. The vertices of the attached complete graph will be, for $v_i$, $\{v_{(i,1)},..... v_{(i,n+r)} \}$ The subgraph is atached to $v_i$ by an edge $(v_i, v_{i,1})$.

It is easy to see that $(X,\lambda)$ is isomorphic to $(X,\mu)$ iff $Z$ is isomorphic to $Z'$. Since there are at most $2n$ distinct labels, the graphs $Z$ and $Z'$ have no more than $2n^2+n$ vortices each and can thus be constructed in polynomial time.

the definition of graph label is given as-

Let $X = (V,E)$ be a graph, $\lambda$ is a mapping from $V$ onto a set $L = \{ l_1,...l_k\}$. Then the pair $(X,\lambda)$ is a labelled graph.

Question 1: Why $k\leq 2n$ which implies $r\leq2n$? It seems that it should be $k\leq n$ since the passage of wikipedia here tells

When used without qualification, the term labeled graph generally refers to a vertex-labeled graph with all labels distinct. Such a graph may equivalently be labeled by the consecutive integers $\{1, …, > |E |\}$, where $|E |$ is the number of vertices in the graph.

Question 2: What is the explanation of -

Since there are at most $2n$ distinct labels, the graphs $Z$ and $Z'$ have no more than $2n^2+n$ vortices each and can thus be constructed in

Thanks in advance.

## 2 Answers

My interpretation:

The Confusion arises, here-

Assume that both $$X$$ and $$X'$$ have $$n$$ vertices. We plan to code the graph labels as suitable subgraphs which we attach to the vertices of $$X$$ and of $$X'$$. In time polynomial in the length of the input we can rename the labels and may assume, therefore, that $$L = \{1 ..... k\}$$ is the set of labels assigned by $$\lambda$$ and $$\mu$$. Note that $$k\leq2n$$ .

One needs to note that-

we can rename the labels and may assume, therefore, that $$L = \{1 ..... k\}$$ is the set of labels

assigned by $$\lambda$$ and $$\mu$$.

So, if you have $$k\leq n$$, then there is a guarantee or certainty,that there exists an Isomorphism from $$X$$ to $$X'$$ already, since, if $$k\leq n$$ then it is certain that $$\exists i,j$$ such that $$\lambda(v_i)=r=\mu(v_j)$$ where $$1\leq i,j \leq n$$.

But if $$k\leq 2n$$, then $$\lambda(v_i)$$ may take $$n$$ different label, and $$\mu(v_j)$$ may take $$n$$ different label.

For example, consider Cyclic Graph $$C_4$$ and Complete Graph $$K_4$$. Add 1 vertex to 1st,2 vertices to 2nd,3 vertices to 3rd, 4 vertices to 4th vertex of $$C_4$$ and $$K_4$$ and rename them as $$C'_4$$ and $$K'_4$$. Now you have to use 14 different labels in $$C'_4$$, and none of them can be used in $$K'_4$$. Note that the number of vertices is same in both $$C'_4$$ and $$K'_4$$. Here, $$|L|=2n=28$$;

So, $$k\leq2n$$.

I think the answer of Jim is good. $k\leq 2 n$ because you have to consider both $\mu$ and $\lambda$. If they have different labels the total number of unique label can be $2n$. (Of course one can argue that if $\lambda$ and $\mu$ does not share the same set of labels that $(X,\lambda)$ and $(X',\mu)$ have no chance to be isomorphic, thus you could first look whether $\mu$ and $\lambda$ share the same labels and then consider $k\leq n$. But that is not the point of the proof here.)

For your second question it is an upper bound of the worst case scenario which gives the bound $2n^2+n$.

The intuition of the proof is to encode the labels of $(X,\lambda)$ and $(X',\mu)$ by connecting the vertices to new fresh vertices. To do this they assume that the labels are between $1$ and $2n$ (which is the first part that confused you). Then they encode that a vertex $v$ has label $j$ by connecting $v$ in $Z$ to $j$ new vertices (note that only $v$ will be connected to this vertices).

So you have to introduce $\lambda(v)$ new vertices for each $v\in X$ in order to build $X$. Thus in $X$ you have exactly $n+\sum_{v\in X}\lambda(v)$ vertices. but you know that $\lambda(v)\leq 2n$ thus you get: \begin{align} |Z| &=n+\sum_{v\in X}\lambda(v) \\ & \leq n+\sum_{v\in X}2n = n+n2n = 2n^2+n \end{align}