I've just randomly* worked out the Bacon-Sabbath number of Bill Bailey, but I doubt he'll have an Erdos number as an arts student who dropped out...
Bacon (2):
Bill Bailey was in The Hitchhiker's Guide to the Galaxy with John Malkovich
John Malkovich was in Queen's Logic with Kevin Bacon
Sabbath (4):
Bill Bailey performed Bill Bailey's Guide to the Orchestra with the BBC Concert Orchestra conducted by Anne Dudley (of the Art of Noise).
Anne Dudley (as the Art of Noise) performed "Kiss" with Tom Jones
Tom Jones's backing groups in the 1960s included session guitarist Ritchie Blackmore, later of Rainbow.
Ritchie Blackmore formed Rainbow with Ronny James Dio of Black Sabbath
*I'm trying to work out who's the best connected QI panellist aside from EBSer Prof. Cox. I've come up with Bill Bailey (no Erdos), Jo Brand (probably no Sabbath), Daniel Radcliffe (probably no Erdos), Ben Goldacre (no detectable Sabbath), Jim Moir (no Erdos, possibly unless books are included), the lovely Sue Perkins (no Erdos) and Howard Goodall (probably no Erdos)