Problem: A (non-directed) graph is called connected if there is a path in the graph between any two vertices. Let L be the language of binary encodings of connected graphs.
(a) Prove that L is in the class NP.
(The input to be verified is a set of potential paths, one connecting each pair of vertices. Each path is given by a list of consecutive vertices. You must verify the potential paths by checking that each step from one vertex to the next is actually an edge on the path.)
(b) Is L in the class P?
(c) If so, try to prove it by writing an algorithm (in pseudo-code) that verifies L in polynomial time.
(d) What would it mean if we could prove that L was not in the class P?