Skip to main content
added 186 characters in body
Source Link

Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$ nor $bya$ for some $y$. Basically if I split my Eulerian trail into paths of length two I want each two points to be endpoints of a single such path.

For prime $n$ I can find such Eulerian trail by just labelling vertices 1,2,...,n and then doing hamiltonian cycles starting from 1 where first cycle goes 1,2,...,n,1 ; second 1,3,5,7,...,n-1,1 and so on. But I am not sure how to do it for composite $n$ since in this case this isn't an Eulerian trail. Does someone have a reference or an idea how this would work?

Edit: Thanks to the comment of Ilya Bogdanov below I see that my attempt was very obviously incorrect. The question of weather such an eulerian trail exists is still interesting to me,

Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$ nor $bya$ for some $y$. Basically if I split my Eulerian trail into paths of length two I want each two points to be endpoints of a single such path.

For prime $n$ I can find such Eulerian trail by just labelling vertices 1,2,...,n and then doing hamiltonian cycles starting from 1 where first cycle goes 1,2,...,n,1 ; second 1,3,5,7,...,n-1,1 and so on. But I am not sure how to do it for composite $n$ since in this case this isn't an Eulerian trail. Does someone have a reference or an idea how this would work?

Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$ nor $bya$ for some $y$. Basically if I split my Eulerian trail into paths of length two I want each two points to be endpoints of a single such path.

For prime $n$ I can find such Eulerian trail by just labelling vertices 1,2,...,n and then doing hamiltonian cycles starting from 1 where first cycle goes 1,2,...,n,1 ; second 1,3,5,7,...,n-1,1 and so on. But I am not sure how to do it for composite $n$ since in this case this isn't an Eulerian trail. Does someone have a reference or an idea how this would work?

Edit: Thanks to the comment of Ilya Bogdanov below I see that my attempt was very obviously incorrect. The question of weather such an eulerian trail exists is still interesting to me,

added 45 characters in body
Source Link

Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$ nor $bya$ for some $y$. Basically if I split my Eulerian trail into paths of length two I want each two points to be endpoints of a single such path.

For smallprime $n$ I can find such Eulerian trail by just labelling vertices 1,2,...,n and then doing hamiltonian cycles starting from 1 where first cycle goes 1,2,...,n,1 ; second 1,3,5,7,...,n-1,1 and so on. But I am not sure if this workshow to do it for some largecomposite $n$ since in this case this isn't an Eulerian trail. Does anyone see whysomeone have a reference or an idea how this approach would clearly fail or work?

Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$ nor $bya$ for some $y$. Basically if I split my Eulerian trail into paths of length two I want each two points to be endpoints of a single such path.

For small $n$ I can find such Eulerian trail by just labelling vertices 1,2,...,n and then doing hamiltonian cycles starting from 1 where first cycle goes 1,2,...,n,1 ; second 1,3,5,7,...,n-1,1 and so on. But I am not sure if this works for some large $n$. Does anyone see why this approach would clearly fail or work?

Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$ nor $bya$ for some $y$. Basically if I split my Eulerian trail into paths of length two I want each two points to be endpoints of a single such path.

For prime $n$ I can find such Eulerian trail by just labelling vertices 1,2,...,n and then doing hamiltonian cycles starting from 1 where first cycle goes 1,2,...,n,1 ; second 1,3,5,7,...,n-1,1 and so on. But I am not sure how to do it for composite $n$ since in this case this isn't an Eulerian trail. Does someone have a reference or an idea how this would work?

Source Link

Eulerian trails in complete graphs

Assume that for some odd $n$ we have a complete graph $K_n$. Is it possible to always find Eluerian trail on $K_n$ such that if we have visited vertices $axb$ then we never before nor after visit $ayb$ nor $bya$ for some $y$. Basically if I split my Eulerian trail into paths of length two I want each two points to be endpoints of a single such path.

For small $n$ I can find such Eulerian trail by just labelling vertices 1,2,...,n and then doing hamiltonian cycles starting from 1 where first cycle goes 1,2,...,n,1 ; second 1,3,5,7,...,n-1,1 and so on. But I am not sure if this works for some large $n$. Does anyone see why this approach would clearly fail or work?