Equidecomposable graphs, unimodality and asymptotics I will call two graphs $G$ and $H$, $r$-equidecomposable (in analogy with Hilbert's third problem) if they can be written as unions of disjoint subgraphs
$$G\cong \bigsqcup_{i=1}^r G_i\quad  ,\quad  H\cong \bigsqcup_{i=1}^r H_i$$
(disjoint here means they have no common edges), and $G_i\cong H_i $ for $1\le i \le r$. Let $\epsilon(G,H)$ be the smallest $r$ for which $G$ and $H$ are $r$-equidecomposable. Let
$$f(n,m)=\max_{G,H\in V(n,m) } \epsilon(G,H) $$
where $V(n,m)$ is the collection of all graphs with $n$ vertices and $m$ edges.
Is the sequence $f(n,m)$ unimodal for fixed $n$? Can one find asymptotics for values such as $f\left(n,\frac{n(n-1)}{4}\right)$ when $n$ is large?
 A: If Joseph is going to take this as an opportunity to show some nice and illustrative pictures, I am going to do similarly, but using words instead.  Gjergji probably already knows what I am going to say, but others might find the remarks a useful stepping stone to the subject.
My initial thought was using a star graph, which on m nodes has a degree sequence of (m-1) 1's and 1 entry of (m-1).  Embedding this into n=2m nodes and choosing H to be a graph of m disconnected edges gives that
n/2 is a lower bound for f(n,n/2) and n even, and an analogous bound for n odd.  Gjergji hints at a better construction in the comments which asymptotically gives a lower bound of 2n/3 .
It so happens that every graph on n nodes is r-decomposable into star graphs for some r less than n.  A nice argument on degree sequences allows one to remove a star graph from
each of G and H leaving at least one vertex in one of the graphs with no edges, and then
a second star graph can be removed from each to guarantee that a vertex in the other
graph has no edges.  This allows us to look at the situation on n-1 nodes and gives
an upper bound of 2n (which can be tightened to 2n-6 for n>3) for f(n,m) for any m.
If there is a relation between decomposability for a pair of graphs and decomposability for their complements, I have not found it yet.  However having min (m, floor(2n/3)) and
2n as upper and lower bounds on parts of f suggests to me that f is unimodal, that
there are nice asymptotics and that for m between n and ((n choose 2) - n), the
asymptotic value for f(n,m) will be Cn for some constant C less than 2, most likely C=1.
Using star graphs for the pieces provides nice results.  It might be good to
consider decomposition into certain graph classes like paths or trees and see what
asymptotics can be found using such restrictions.
Gerhard "Ask Me About System Design" Paseman, 2012.05.11
A: Not an answer (cool question!), 
just an excuse to show a pair of 2-equidecomposable graphs, one planar, one not:

          
