# graph to tree and graph isomorphism problem

Sorry if the following are stupid questions (i do not know much about the graph theory).

1. Motivation

we do not know the graph isomorphism problem in class P or NP complete and it is P in the case trees (see http://en.wikipedia.org/wiki/Graph_isomorphism_problem).

2. Transformation a graph to tree

Let $G$ be a simple connect graph with $v$ vertices and $e$ edges. We consider the following process:

Process: If $G$ is not a tree we will have a cycle in $G$, called $C_k$ with vertices (assume that) $v_1,...,v_k$. Then

• We add a new vertex $w$ to $G$
• delete $k$ edges of $C_k$: $(v_1,v_2),...,(v_k, v_1)$.
• Add $k$ edges $(w,v_1),...,(w,v_k)$ to the graph.

We obtain a new graph $G'$ with $v+1$ vertices and $e$ edges.

Theorem. Applying the above process $v - e + 1$ times we get a tree $T$.

Notice that we may get many trees by different processes.

Question 1. Assume that we always choice $C_k$ such that $k$ as small as possible. Is it true that every tree we obtain are isomorphism?

I do not know this question true or false. In the case we have a negative in general, which condition it is true?

3. The graph isomorphism problem

In the case Question 1 has an affirmative answer for each $G$ we get a tree $T(G)$ (up to an isomorphism).

Question 2. Assume that $G$ and $H$ are simple connect graph with same number of vertices, edges, degrees of vretex,... (we can need more condition which easy to check). Whether $G$ and $H$ are isomorphism iff $T(G)$ and $T(H)$ are isomorphism?

-