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?