1 Given a graph G (V, E), a vertex cover in G is a subset V' V such that for all (uw) e E,u E V' or w e 4 Figure 1 Figure 1 shows an undirected graph including 6 nodes. Answer the questions below: Does Figure 1 have a vertex cover including four nodes? If so, given an example of 4-node vertex cover? Does Figure 1 have a vertex cover including three nodes? If so, given an example of 3-node vertex cover? 1. 2. 3. What is the minimum vertex cover (including least nodes) in Figure 1? 4. Let VC kG, k> | G has a VC of size s kj. Is this problem a NP problem? Prove your conclusion 5. Is VC a NP-complete problem? Why? 1 Given a graph G (V, E), a vertex cover in G is a subset V' V such that for all (uw) e E,u E V' or w e 4 Figure 1 Figure 1 shows an undirected graph including 6 nodes. Answer the questions below: Does Figure 1 have a vertex cover including four nodes? If so, given an example of 4-node vertex cover? Does Figure 1 have a vertex cover including three nodes? If so, given an example of 3-node vertex cover? 1. 2. 3. What is the minimum vertex cover (including least nodes) in Figure 1? 4. Let VC kG, k> | G has a VC of size s kj. Is this problem a NP problem? Prove your conclusion 5. Is VC a NP-complete problem? Why