How to know if X and Y have coauthored? 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:

author:foo author:bar


As always with Google Scholar, double-check the results.