<p>The main problem is that Statement I is false, as @Marek just said.
There are different graphs transformed into the same graph.</p>

<p>For a concrete example, both (a) <em>tetrahedron</em> (double edges) 
and (b) <em>octahedron</em> 
transformed into (c) <em>truncated octahedron</em>.</p>

<p>(a) <img src="https://i.sstatic.net/ruYEJ.jpg" width="150" height="150">
(b) <img src="https://i.sstatic.net/AsOuw.jpg" width="150" height="150">
(c) <img src="https://i.sstatic.net/2xtDM.jpg" width="150" height="150"></p>

CC BY-SA 2.5
2011-02-18T17:46:56.337Z
Good! But (b) has multiple edges between its nodes. How about graphs without multiple edges between nodes? Are there families of graphs for where this could work?
Pratik Deoghare
CC BY-SA 2.5
2011-02-18T18:07:32.813Z
Also, (a) has 6 nodes and (b) has only 4 nodes. In the algorithm only graphs with same number of vertices and edges will be allowed. Because we can discard them in polynomial time. I am sorry I should have specified this earlier.
Pratik Deoghare
CC BY-SA 2.5
2011-02-18T19:58:37.973Z
In its "second level", (c) has some nodes of degree two. I can not see wether it remains a counterexample after fixing (c).
Raphael
CC BY-SA 2.5
2011-02-19T05:20:40.073Z
@Raphael: Sorry some of the edges are misdrawn. I'll fixed it soon. @TheMachineCharmer: I guess we can construct conunterexamples with larger faces. Update soon!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-21T13:45:32.257Z
I cannot find any concrete examples with equal number of nodes and without multiple edges. And currently I believe that the main obstacle to the method is the one described [by David](http://cstheory.stackexchange.com/questions/5003/is-this-graph-transformation-unique-up-to-isomorphism/5009#5009). Maybe after new concrete examples founded I'll revise my answer.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-18T17:33:17.207Z
2011-02-21T14:14:47.463Z
2011-02-21T14:14:47.463Z
Hsien-Chih Chang 張顯之
<p>Your Statement I is not true. You can have two non-isomorphic graphs G1, G2 with T(G1), T(G2) isomorphic. Basically, the problem is that there is no reason why isomorphisms between T(G) graphs should map vertex-cycles into vertex-cycles. </p>

CC BY-SA 2.5
2011-02-18T17:10:05.623Z
2011-02-18T17:10:05.623Z
Marek Chrobak
<p>Along with the already-given answers stating the existence of two graphs G1≠G2 for which T(G1)=T(G2), there is also a different problem: there exist pairs G1=G2 for which T(G1)≠T(G2). This is because the transformation depends not just on the isomorphism class of G, but also on the cyclic ordering of the edges around each vertex of G.</p>

<p>Edited to add an example based on Mark Reitblatt's comment:
<img src="https://i.sstatic.net/FkDKH.png" alt="enter image description here"></p>

CC BY-SA 2.5
2011-02-18T19:47:32.647Z
You are saying $T$ is not well-defined (for canonical graph definitions), which renders the question ill-posed.
Raphael
CC BY-SA 2.5
2011-02-18T20:37:04.300Z
@David Eppstein: I can not understand anything. Would you please elaborate? Perhaps with an example. Please.
Pratik Deoghare
CC BY-SA 2.5
2011-02-18T21:29:28.197Z
@TheMachineCharmer Consider a node with 4 edges. When you split it into 4 nodes, you have to make a choice about which new node gets which old edge. This choice will impose an (adjacency) ordering on the new nodes that didn't exist on the old edges. Try it with a node that's connected to 4 different subgraphs, A B C and D. Is the A node adjacent to the B node? Depends on the ordering. But in the old graph, all the edges from this node were adjacent.
Mark Reitblatt
CC BY-SA 2.5
2011-02-19T05:24:01.177Z
Now its clear to me. btw which software are you using for making these graphs?
Pratik Deoghare
CC BY-SA 2.5
2011-02-19T05:34:26.243Z
Adobe Illustrator.
David Eppstein
CC BY-SA 2.5
2011-02-19T08:21:19.127Z
David, you should add labels to the inner circle's nodes. As it is, the unequalness is not (crystal) clear. Also, the resulting graphs are isomorphic; that is, if we could deterministically choose one possible $T(G)$, we might still be fine. (I cringe since the counterexample bases on the visual intuition of maintaining order around a node -- an order that does not exist in the graph. But well, this is how the OP started it.)
Raphael
CC BY-SA 2.5
2011-02-19T17:06:10.787Z
I think labels would actually be more confusing, because there is more than one way to correctly label each graph, so the labels would add information not already present in the isomorphism instance.
David Eppstein
CC BY-SA 3.0
2011-08-15T05:44:20.840Z
@David Eppstein Nice pictures! How do you make them?
v s
CC BY-SA 2.5
2011-02-18T19:08:14.943Z
2011-02-19T04:34:01.700Z
2011-02-19T04:34:01.700Z
David Eppstein
<p>Suppose, transformation <code>T</code> is defined as given in the diagrams below. 
Every vertex (<code>v</code>) is replaced by <code>deg(v)-gon</code>. And then graph is reconnected as shown.</p>

<p><img src="https://i.sstatic.net/hASj2.jpg" alt="enter image description here"></p>

<p><em>Those on the left are <code>G</code>s and on the right are <code>T(G)</code>s.</em></p>

<p>It is easy to see that every vertex in  <code>T(G)</code> has degree <code>3</code>. 
<a href="http://ix.cs.uoregon.edu/~luks/iso.pdf" rel="nofollow noreferrer">This paper</a> claims that graph isomorphism of such graphs can be tested in polynomial time. Also, <code>G</code> can be converted to <code>T(G)</code> in polynomial time. </p>

<p><strong>Statement I:</strong> G1 and G2 are isomorphic iff T(G1) and T(G2) are isomorphic.<br>
<strong>EDIT:</strong>
Specifications for G1,G2:</p>

<ol>
<li>G1 = (V1,E1) and G2=(V2,E2) </li>
<li>|E1| = |E2| and |V1| = |V2|</li>
<li>Sort[{deg(v)|v in V1}] = Sort[{deg(u)| u in V2}]</li>
</ol>

<p>If <strong>Statement I</strong> is <code>True</code> then do we have solution for GI problem? </p>

<p><em>Note: I am n00b in this field. I invent funny techniques daily.</em> </p>

CC BY-SA 2.5
2011-02-18T17:14:24.793Z
I don't understand why every vertex in $T(G)$ has degree $3$. If you have a vertex in $G$ with degree $1$ it has also degree $1$ in $T(G)$ or not?
Marc Bury
CC BY-SA 2.5
2011-02-18T17:50:29.203Z
No. Suppose there is a vertex with degree 1. Then it will become a vertex with self-loop. Self-loop will add 2 degrees.
Pratik Deoghare
CC BY-SA 2.5
2011-02-18T19:51:49.147Z
Considering a solver for GI as goal, you should copy the exact graph definition from GI here. I was under the impression that all standard graph problems were formulated with simple graphs, but I might be wrong there.
Raphael
CC BY-SA 2.5
2011-02-18T19:53:25.747Z
If you tried replacing your example-driven picture by a formal definition of $T$, you would discover the flaw David has pointed out. (General advice for developing "funny techniques" ;))
Raphael
CC BY-SA 2.5
2011-02-18T20:34:54.973Z
@Raphael Suppose nodes connected to any node $v$ pull $v$ so hard that it explodes into pieces but pieces are still connected. That is approximately what I mean by $T$. I am working on formal definition. And thanks! for your advice.:)) I think I need to learn some notation if I don't want to end up as science fiction writer.:)
Pratik Deoghare
CC BY-SA 2.5
2011-02-18T21:06:46.177Z
What is this $T$ formally called?
Pratik Deoghare
CC BY-SA 2.5
2011-02-18T22:11:06.050Z
If you want this to work, you need $T$ to be an *injective function*. Sadly, your idea is not a function.
Raphael
CC BY-SA 2.5
2011-02-19T01:39:29.423Z
Putting to the side the issues about isomorphism, the graph operation suggested by the top diagram, when applied to planar 3-connected graphs (which are the 3-polytopal graphs), corresponds to the idea of truncation of a vertex of the polytope associated with the graph. In particular, the new graph will be planar and 3-connected and sometimes reflects nice properties of the original polytope. For example, if one has a hamiltonian polytope and truncates a 3-valent vertex one gets a new 3-polytope which still has a hamiltonian circuit.
Joseph Malkevitch
CC BY-SA 2.5
2011-02-19T05:35:34.877Z
@Joseph Searching for truncation is giving me good results. Is this generalization of truncation?  what is it formally called?   @Raphael No problem. I have many more GI algos. lol.
Pratik Deoghare
CC BY-SA 2.5
2011-02-19T16:04:40.973Z
Truncation is a natural operation on polytopes but I am not sure this is necessarily a good name for something more general. Another natural operation polytopes is an edge shave. On a 3-valent 3-polytope this replaces an edge by a 4-gon.
Joseph Malkevitch
<ds.algorithms><graph-theory><co.combinatorics><advice-request><graph-isomorphism>
Is this graph transformation unique up to isomorphism? [Answer:NO]
Pratik Deoghare
# Is this graph transformation unique up to isomorphism? [Answer:NO]

(Asked by: username_0 on 2011-02-18)

Suppose, transformation `T` is defined as given in the diagrams below.
Every vertex (`v`) is replaced by `deg(v)-gon`. And then graph is reconnected as shown.

![enter image description here](https://i.sstatic.net/hASj2.jpg)

*Those on the left are `G`s and on the right are `T(G)`s.*

It is easy to see that every vertex in `T(G)` has degree `3`.
[This paper](http://ix.cs.uoregon.edu/~luks/iso.pdf) claims that graph isomorphism of such graphs can be tested in polynomial time. Also, `G` can be converted to `T(G)` in polynomial time.

**Statement I:** G1 and G2 are isomorphic iff T(G1) and T(G2) are isomorphic.  
**EDIT:**
Specifications for G1,G2:

1. G1 = (V1,E1) and G2=(V2,E2)
2. |E1| = |E2| and |V1| = |V2|
3. Sort[{deg(v)|v in V1}] = Sort[{deg(u)| u in V2}]

If **Statement I** is `True` then do we have solution for GI problem?

*Note: I am n00b in this field. I invent funny techniques daily.*

**Tags:** ds.algorithms, graph-theory, co.combinatorics, advice-request, graph-isomorphism
> **Comments:**
> **username_1**: I don't understand why every vertex in $T(G)$ has degree $3$. If you have a vertex in $G$ with degree $1$ it has also degree $1$ in $T(G)$ or not?  
> **username_0**: No. Suppose there is a vertex with degree 1. Then it will become a vertex with self-loop. Self-loop will add 2 degrees.  
> **username_2**: Considering a solver for GI as goal, you should copy the exact graph definition from GI here. I was under the impression that all standard graph problems were formulated with simple graphs, but I might be wrong there.  
> **username_2**: If you tried replacing your example-driven picture by a formal definition of $T$, you would discover the flaw David has pointed out. (General advice for developing "funny techniques" ;))  
> **username_0**: @Raphael Suppose nodes connected to any node $v$ pull $v$ so hard that it explodes into pieces but pieces are still connected. That is approximately what I mean by $T$. I am working on formal definition. And thanks! for your advice.:)) I think I need to learn some notation if I don't want to end up as science fiction writer.:)  
> **username_0**: What is this $T$ formally called?  
> **username_2**: If you want this to work, you need $T$ to be an *injective function*. Sadly, your idea is not a function.  
> **username_3**: Putting to the side the issues about isomorphism, the graph operation suggested by the top diagram, when applied to planar 3-connected graphs (which are the 3-polytopal graphs), corresponds to the idea of truncation of a vertex of the polytope associated with the graph. In particular, the new graph will be planar and 3-connected and sometimes reflects nice properties of the original polytope. For example, if one has a hamiltonian polytope and truncates a 3-valent vertex one gets a new 3-polytope which still has a hamiltonian circuit.  
> **username_0**: @Joseph Searching for truncation is giving me good results. Is this generalization of truncation?  what is it formally called?   @Raphael No problem. I have many more GI algos. lol.  
> **username_3**: Truncation is a natural operation on polytopes but I am not sure this is necessarily a good name for something more general. Another natural operation polytopes is an edge shave. On a 3-valent 3-polytope this replaces an edge by a 4-gon.  

---

## 3 answers

### Answer by username_6 on 2011-02-18. Score: 23 | Accepted answer

Along with the already-given answers stating the existence of two graphs G1≠G2 for which T(G1)=T(G2), there is also a different problem: there exist pairs G1=G2 for which T(G1)≠T(G2). This is because the transformation depends not just on the isomorphism class of G, but also on the cyclic ordering of the edges around each vertex of G.

Edited to add an example based on Mark Reitblatt's comment:
![enter image description here](https://i.sstatic.net/FkDKH.png)

> **Comments:**
> **username_2**: You are saying $T$ is not well-defined (for canonical graph definitions), which renders the question ill-posed.  
> **username_0**: @David Eppstein: I can not understand anything. Would you please elaborate? Perhaps with an example. Please.  
> **username_7**: @TheMachineCharmer Consider a node with 4 edges. When you split it into 4 nodes, you have to make a choice about which new node gets which old edge. This choice will impose an (adjacency) ordering on the new nodes that didn't exist on the old edges. Try it with a node that's connected to 4 different subgraphs, A B C and D. Is the A node adjacent to the B node? Depends on the ordering. But in the old graph, all the edges from this node were adjacent.  
> **username_0**: Now its clear to me. btw which software are you using for making these graphs?  
> **username_6**: Adobe Illustrator.  
> **username_2**: David, you should add labels to the inner circle's nodes. As it is, the unequalness is not (crystal) clear. Also, the resulting graphs are isomorphic; that is, if we could deterministically choose one possible $T(G)$, we might still be fine. (I cringe since the counterexample bases on the visual intuition of maintaining order around a node -- an order that does not exist in the graph. But well, this is how the OP started it.)  
> **username_6**: I think labels would actually be more confusing, because there is more than one way to correctly label each graph, so the labels would add information not already present in the isomorphism instance.  
> **username_8**: @David Eppstein Nice pictures! How do you make them?  

---

### Answer by username_4 on 2011-02-18. Score: 9

The main problem is that Statement I is false, as @Marek just said.
There are different graphs transformed into the same graph.

For a concrete example, both (a) *tetrahedron* (double edges)
and (b) *octahedron*
transformed into (c) *truncated octahedron*.

(a) ![](https://i.sstatic.net/ruYEJ.jpg)
(b) ![](https://i.sstatic.net/AsOuw.jpg)
(c) ![](https://i.sstatic.net/2xtDM.jpg)

> **Comments:**
> **username_0**: Good! But (b) has multiple edges between its nodes. How about graphs without multiple edges between nodes? Are there families of graphs for where this could work?  
> **username_0**: Also, (a) has 6 nodes and (b) has only 4 nodes. In the algorithm only graphs with same number of vertices and edges will be allowed. Because we can discard them in polynomial time. I am sorry I should have specified this earlier.  
> **username_2**: In its "second level", (c) has some nodes of degree two. I can not see wether it remains a counterexample after fixing (c).  
> **username_4**: @Raphael: Sorry some of the edges are misdrawn. I'll fixed it soon. @TheMachineCharmer: I guess we can construct conunterexamples with larger faces. Update soon!  
> **username_4**: I cannot find any concrete examples with equal number of nodes and without multiple edges. And currently I believe that the main obstacle to the method is the one described [by David](http://cstheory.stackexchange.com/questions/5003/is-this-graph-transformation-unique-up-to-isomorphism/5009#5009). Maybe after new concrete examples founded I'll revise my answer.  

---

### Answer by username_5 on 2011-02-18. Score: 5

Your Statement I is not true. You can have two non-isomorphic graphs G1, G2 with T(G1), T(G2) isomorphic. Basically, the problem is that there is no reason why isomorphisms between T(G) graphs should map vertex-cycles into vertex-cycles.


---

