Question

Show that if there is an Euler cycle in the graph, there is an Euler cycle in any BCC of the graph

Answer 1

`Hey,

Note: Brother in case of any queries, just comment in box I would be very happy to assist all your queries

Theorem: If there is an Euler cycle in the graph, there is an Euler cycle in any BCC of the graph.

Proof:

Assuming that a cycle that includes every edge exactly once is called an Eulerian cycle.

Let G be a connected graph. Then G has an Eulerian cycle if and only if all nodes have even degree.

Fix some cycle, and orient the edges by the direction that the cycle traverses them. Then in the resulting directed graph we must have ?^-(u) = ?⁺(u) for all u, since every time we enter a vertex we have to leave it again. But then ?(u) = 2?⁺(u) is even.

Suppose now that ?(u) is even for all u. We will construct an Eulerian cycle on all nodes in any BCC of the graph by induction on |E|. The base case is when |E| = 2|V| and G = C_|V|. For a larger graph, choose some starting node u₁, and construct a path u₁u₂... by choosing an arbitrary unused edge leaving each u_i; this is always possible for u_i?u₁ since whenever we reach u_i we have always consumed an even number of edges on previous visits plus one to get to it this time, leaving at least one remaining edge to leave on. Since there are only finitely many edges and we can only use each one once, eventually we must get stuck, and this must occur with u_k = u₁ for some k. Now delete all the edges in u₁...u_k from G, and consider the connected components of G-(u₁...u_k). Removing the cycle reduces ?(v) by an even number, so within each such connected component the degree of all vertices is even. It follows from the induction hypothesis that each connected component has an Eulerian cycle. We'll now string these per-component cycles together using our original cycle: while traversing u₁...,u_k when we encounter some component for the first time, we take a detour around the component's cycle. The resulting merged cycle gives an Eulerian cycle for the entire graph.

Now consider the conditions of the graph,

If graph has no odd degree vertex, there is at least one Eulerian Circuit. If graph as two vertices with odd degree, there is no Eulerian Circuit but at least one Eulerian Path. If graph has more than two vertices with odd degree, there is no Eulerian Circuit or Eulerian Path.

If the cycle contains all the edges of E of G, we are done. Otherwise, denote the edges of the cycle E', the nodes on it with the outdegree (and hence the indegree) equal to 1 V', and consider the graph G' = G(V - V', E - E'). Since G is connected, the cycle could not be a connected component (unless it's an Euler cycle, which we assumed it is not). If so, every connected component of G' shares at least one vertex with the cycle. Start with those vertices to find a cycle in each of the connected components of G'. Continue in this manner until no edges remain.

From the above proof and given consideration it is clear that if there is an Euler cycle in the graph then there must be a Euler cycle in any BCC of the graph or a directed graph.

Kindly revert for any queries

Thanks.