
graphs
can someone please help me with this difficult question cant quite figure out where to start
thanks in advance
pls note (<= means less than or equal to, >= means greater than or equal to)
edgar
(a) Of what must a connected graph in which every vertex has degree <= 2 consist? Prove your answer.
(b) Let G be any graph in which every vertex has degree <= 2. Describe G. How would you calculate the size of a maximal independent set of vertices of G?
(c) Write an algorithm MaxIndepSet3 for calculating the size of the largest independent set ofvertices: its trivial case is when no vertex has degree >= 3otherwise it proceeds as in MaxIndepSet2