River Crossing Problem (Graph Theory)

[Jeff121]

Considering the problem of transporting n items across a river using a boat that can carry k items, where some pairs of items cannot be left together unsupervised. Let G be the simple graph whose vertices correspond to items, and whose edges join pairs of items that need supervision.

 

How do I show that the minimum size of a boat k for which a solution exists is either Vc(G) or Vc(G)+1, where Vc(G) is the size of a minimum vertex cover of G.

Edited October 16, 2016 by Jeff121