Question $8$: Since Taylor Swift and Travis Kelce miss each other very much, they decide

to meet. Taylor and Travis live in a connected, undirected, non$-$bipartite graph $G=(V,E).$

Taylor lives at vertex $s,$ whereas Travis lives at vertex $k.$

Taylor and Travis move in steps. In each step, Taylor must move from her current vertex

to a neighboring vertex, and Travis must move from his current vertex to a neighboring

vertex.

Prove that there exists a moving strategy such that Taylor and Travis meet each other

at the same vertex.

Hint: While moving around in the graph, $londots.......$ r and Travis may visit the same

vertex more than once, and may traverse the same edge more than once.

If the graph $G$ consists of the single edge $\{s,k\},$ then they will never be at the same

vertex. But in this case $G$ is bipartite.

If the graph contains a path having $8$ edges, Taylor lives at one end$-$vertex, and Travis

lives at the other end$-$vertex, will they ever be at the same vertex?

Question $7$ is useful.