MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
we choice one of them and get a new graph. – Pham Hung Quy Jul 4 '12 at 9:55
one process we choice one cycle. – Pham Hung Quy Jul 4 '12 at 9:57
If you try the different possible processes with the graph suggested by Brendan, you will see that the answer to question 1 is no. – nvcleemp Jul 4 '12 at 10:20
Thanks you a lost! – Pham Hung Quy Jul 4 '12 at 13:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.