I suppose if you choose edges at random, then it's as likely to fail early as it is to fail late. So if you get to 70% confidence, that does seem reasonable to believe it's probably 3-colorable (but still with a big chance that it is not).