Question

An xy trail M is greedy if every edge incident to y is contained in M. Let H be an Eulerian graph, and let x be a vertex in H. Prove that every greedy trail starting from x is a Eulerian circuit iff every cycle in H contains x.

Answer 1

A closed walk in a graph H containing all the edges of H is called an Euler line in H. A graph containing an Euler line is called an Euler graph. We know that a walk is always connected. Since the Euler line (which is a walk) contains all the edges of the graph, an Euler graph is connected except for any isolated vertices the graph may contain. As isolated vertices do not contribute anything to the understanding of an Euler graph, it is assumed now onwards that Euler graphs do not have any isolated vertices and are thus connected.

Theorem :- (Euler) A connected graph H is an Euler graph if and only if all vertices of G are of even degree. Proof Necessity Let H(V, E) be an Euler graph. Thus H contains an Euler line Z, which is a closed walk. Let this walk start and end at the vertex x ∈ V. Since each visit of Z to an intermediate vertex y of Z contributes two to the degree of y and since Z traverses each edge exactly once, d(y) is even for every such vertex. Each intermediate visit to x contributes two to the degree of x, and also the initial and final edges of Z contribute one each to the degree of x. So the degree d(x) of x is also even. Sufficiency Let H be a connected graph and let degree of each vertex of H be even. Assume H is not Eulerian and let H contain least number of edges. Since δ ≥ 2, H has a cycle. Let Z be a closed walk in H of maximum length. Clearly, H−E(Z) is an even degree graph. Let C1 be one of the components of H−E(Z). As C1 has less number of edges than H, it is Eulerian and has a vertex y in common with Z. Let Z 0 be an Euler line in C1. Then Z 0 ∪Z is closed in H, starting and ending at v. Since it is longer than Z, the choice of Z is contradicted. Hence G is Eulerian.