Eternal Vertex Cover Approximation

In the eternal vertex cover problem, policewomen occupy vertices of a graph (CandyLand). When an edge is attacked, at least one endpoint must currently have a policewoman and one endpoint policewoman must traverse the attacked edge. Other policewomen may move to neighboring vertices (at most one step). Lata succeeds if she can defend forever against any attack sequence.

A 4-cycle graph representing CandyLand

Part A

Suppose Lata figures out a way of placing policemen so that no matter where the Demon attacks, Lata can move the policewomen to protect the city. In other words, Lata has managed to find a configuration that keeps the city safe against one attack. Consider the vertices occupied by policewomen. This subset of vertices forms a:

Part B

Suppose the graph of Candyland is a path on seven vertices $v_1, \ldots, v_7$ and Lata places three policewomen on the vertices $$v_2, v_4, v_6$$ . What is the minimum number of attacks the Demon needs to destroy Candyland?

Part C

Suppose the city of CandyLand has 6 houses which are connected by roads as shown in the image below and Lata has placed the policewomen placed at houses A, D and F (as shown in the image), what is the smallest number of attacks in which the Demon is able to destroy the city?

Question diagram

Part D

Suppose Lata finds a maximal matching $$M$$ the Candyland graph and places a policewoman on each of the houses corresponding to both endpoints of the edges $$M$$ . Can she defend attacks from the Demon forever if she does this?

Part E

Suppose Lata finds a maximum matching $$M$$ the Candyland graph and places a policewoman on each of the houses corresponding to both endpoints of the edges $$M$$ . Can she defend attacks from the Demon forever if she does this?

Part F

Suppose we are interested in the smallest number of policewomen that Lata needs to deploy to keep Candyland safe forever. Then: