Hello! 

Let: 
GI=<<g1,g2>: g1 and g2 are graphs and g1 is isomorphic to g2> 
GNI=<<g1,g2>: g1 and g2 are graphs and g1 is not isomorphic to g2> 

It's not yet known whether graph isomorphism (GI) language is in P or
not, and it's not even known if graph non-isomorphism (GNI) language
is in NP or not. Nevertheless, despite an effort, I haven't been able
to find a pair of graphs for which I CAN'T decide isomorphicness, i.e.
can't decide if they are isomorphic or not.

In a simple answer I'd be satisfied by obtaining a single pair of
graphs of "reasonable size" (i.e. a size that I can easily handle in a
normal computer) for which I can't say if they are isomorphic or
non-isomorphic. For the sake of objectivity, I say that any of the
following would satisfy me:
- two graphs with about 1000 edges, for which I can't decide the
isomorphic/non-isomorphic property within 12 hours. (algorithmic
runnning time in a 2,4GHz PC with 512MB RAM)
- two graphs each with about 10000 edges, for which I can't decide the
isomorphic/non-isomorphic property within a week. (algorithmic
runnning time in a 2,4GHz PC with 512MB RAM)

If a more complete answer is possible, I'd like a family of pair of
graphs for which there is a "big" proportion of them for which its
"hard" to decide "isomorphicness".

Thanks! 
Criptog 

Note: I already posted a similar (although simpler) question in the
newsgroup "Graph Theory Algorithms" in
http://groups.google.pt/group/Graph-Theory-Algorithms-/browse_frm/thread/1540eec9010eeb69?hl=pt-PT