Exercise 9.

Below is a graph representing friendships between a group of students (each vertex is a student and each edge is a friendship). Is it possible for the students to sit around a round table in such a way that every student sits between two friends? What does this question have to do with paths?

A complicated graph containing 9 vertices arranged in a circle. If we call the vertex at the top of the circle 1, and number them proceeding clockwise, then vertex 1 is adjacent to 2, 4, 6, and 7. Vertex 2 is also adjacent to 4 and 7. Vertex 3 is adjacent to 6 and 8. Vertex 4 is adjacent to 6, 7, 8, and 9. Vertex 5 is adjacent to 6, 8, and 9. Vertex 7 is also adjacent to 8.
Hint.
in-context