graph traversal proof Jerry is planning to visit every city in the state S. Jerr

Question

graph traversal proof

Jerry is planning to visit every city in the state S. Jerry can buy only two flight tickets. Jerry can land in any city A in the state S and he can depart from any city B in the state S, but inside the state he can only commute by car. Between any two cities in the state S there is exactly one highway - so the network of roads can be represented by a complete graph. Jerry does not stop in any city more than once. Additionally each highway is a one-way highway. Prove that there exists cities A and B and a path from A to B, such that Jerry will visit every city exactly once. Note: you need to prove existence of such A, B and a path from A to B for any for any given configuration of the highway’s one way directions. A complete graph is a simple graph with an edge between any two vertices.

Explanation / Answer

Note: you need to prove existence of such A, B and a path from A to B for any for any given configuration of the highway’s one way directions.

This isn't possible. Consider the following graph

C ->D, C->B, C-A, B->D, B->A, D->A this is one possible configuration of one way highways there aren't any two vertices so that Jerry can visit ever vertex.

This question should be prove or disprove. Please correct me If I am wrong.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.