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?
