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? 



graph to tree and graph isomorphism problem
If two cycles of minimum length have a common edge, then it matters which is chosen. Try two triangles with a common edge, plus one more vertex joined to an apex of one of the triangles.


