Checking if two graphs have the same universal cover

Two finite graphs have the same universal cover iff they have a common finite cover. This surprising fact was first proved by Tom Leighton here:

Frank Thomson Leighton, Finite common coverings of graphs. 231-238 1982 33 J. Comb. Theory, Ser. B

I'm quite sure the paper also presents an algorithm for determining if this is the case for two given graphs; essentially you develop a refined "degree" sequence for the graphs, starting from "# of vertices of degree k" and refining to "# of vertices of degree k with so-and-so neighbors of degree l" etc.

As an aside, the reason this result is so surprising is that it says something highly non-trivial about groups acting on trees (any two subgroups of Aut(T) with a finite quotient are commensurable, up to conjugation), and proving this result directly via group-theoretic methods is surprisingly difficult (and interesting). There's a paper of Bass and Kulkarni which pretty much does just that.

Edit: I just ran a quick search and found this sweet overview: "On Leighton's Graph Covering Theorem".

An addendum on the question of polynomial time. In a 1991 paper, which can be found here, Abello, Fellows, and Stillwell proved that there is a fixed graph H for which the problem of deciding whether a given G covers H is NP-complete.

If two graphs have a common cover, then they have a common universal cover. The "maximal" cover is therefore unique. In general, the reverse is not true. The "minimal" common cover may not be unique. This was shown by Wilfried Imrich and me. See also European Journal of Combinatorics Volume 29, Issue 5, July 2008, Pages 1116-1122