Q: Can we travel along a graph starting at a vertex and returning to it by traversing each edge if the graph exactly once ?
This could be IFF the Graph has Euler circuit "Graph is Eulerian"
Q: Can we travel along a graph starting at a vertex and returning to it by visiting each vertex exactly once ?
This could be IFF the Graph has Hamilton circuit "Graph is Hamiltonian"
"Both questions are an old puzzles "
** A river in the city of Konigsberg, divide the city in four parts as shown
The question is there are Seven bridges of Konigsberg, is it possible to start at some location in the town, (Konigsberg, Russia) travel a cross all the bridges without crossing and bridge twice and return to the starting point ?
There is no way to cross all the bridges without crossing any bridge twice ,Euler solves this problem in 1736 , by definition he gave that a connected multi graph has an Euler circuit IFF its vertices has even degree (paths).
Tags:
Combinatorial