An Euler circuit $v_1,v_2,v_3,\dots,v_n,v_1$ is a triangle-free Euler circuit if and only if there do not exist four consecutive nodes $v_i,v_{i+1},v_{i+2},v_{i+3}$ with $v_i = v_{i+3}$.

Now what are the properties of a graph which does not have such an Euler circuit; i.e., every Euler circuit has a triangle in it.

For example, it is not a bipartite graph.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.