I like to introduce Vertex-Cover as a problem in which the underlying graph models a museum, so that the vertices represent the museum rooms and the edges represent the corridors. Then, it is easy for the students to understand that minimising the number of guards required to watch over the museum corresponds to finding a vertex cover. The guards are placed at the doors of the selected rooms (vertices) and cover the corresponding corridors (edges).