Mathematics — Graph Theory · cycles-walks-graph-theory
Problem
Let G be a simple graph.
(a) Prove that if G has a closed walk of odd length, then G has a cycle of odd length.
(b) Is it true that if G has a closed walk of length not divisible by 3, then G has a cycle of length not divisible by 3?
(c) Does the answer to part (b) change if we replace ``walk'' by ``non-backtracking walk''? (A walk w with edges e1,e2,…,ek (in this order) is said to be non-backtracking if each i∈{1,2,…,k−1} satisfies ei=ei+1.)
(d) A trail (in a graph) means a walk whose edges are distinct (but whose vertices are not necessarily distinct). Does the answer to part (b) change if we replace ``walk'' by ``trail''?
(Proofs and counterexamples should be given.)