# Is there any way to check if one graph is the result of identification and/or splitting on another graph?

Does some algorithm exist that can be used to check if graph $A$ and graph $B$ are related only by combining or separating vertices?

Also, would this be possible if vertices had values (a vertex's value, when split, would be shared in some proportion with the new two vertices).

Approaching this from a brute-force point of view would be too computationally expensive.

-
What does it mean to combine or separate vertices? – Jernej Jun 20 '12 at 18:15
Gerry's answer is exactly what I meant. Combining is contracting. – 827 Jun 21 '12 at 13:57

Graph Contractability. Given graphs $G,H$, can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions? Proved NP-complete by Statman in 1976 (private communication), by transformation from 3-Satisfiability.