It was claimed that anyone involved in the Hollywood film industry can be linked through their film roles to Kevin Bacon within six steps. You are suspicious of such a claim and decide to verify it...

It was claimed that anyone involved in the Hollywood film industry can be linked through their film roles to Kevin Bacon within six steps. You are suspicious of such a claim and decide to verify it using the given dataset.
Before you start to verify the claim, you first notice that it is not possible for this claim to be true if the actor graph is not even connected. Briefly explain how you can verify a given undirected graph is connected (i.e there exists a path between any two actors in the graph). Include the runtime of your algorithm as well.