Is there any tool where one can figure out if two people have coauthored or not? Like the tool where one can figure out somebody's Erdos _number_ .
In computer science, DBLP might be a better idea than MathSciNet. Your own page in DBLP lists all your coauthors; the database is certainly not complete, but usually the information is correct.
You can also try to use Google Scholar, with a search similar to this:
As always with Google Scholar, double-check the results.
It uses the same database as DBLP. It can be used both online or offline. You must download the whole DBLP database (~ 60MB) in order to use it offline.
There is also Microsoft Academic Search if you're looking for graphical display of coauthor graphs, although it does not appear to be a finished product content-wise.