In this problem you will develop an alternative proof to show that every connect

Question

In this problem you will develop an alternative proof to show that every connected graph in which every vertex has even degree contains an eulerian cycle. Below are the steps in the proof. Your task is to fill in the details – make sure to give your reasoning for each step, and that the overall reasoning is logically tight. Step 1. Let ??0??1?????? be a longest path in the graph that contains every edge at most once. Step 2. Prove that the longest path traverses every edge incident to ????. Step 3. Prove that ????=??0. This means that the longest path is a cycle. Step 4. If the longest cycle is not eulerian, there exists an edge that is not in the cycle. Argue that there must therefore exist an edge (??,????) that is not on the longest cycle while ???? is on the longest cycle. Step 5. Now construct a path that is longer than the longest path to arrive at a contradiction.      

Explanation / Answer

Solution:

step 1:

The longest path in the graph will be the path which is visiting every edge exactly once; if it exists.

We can say this is correct. but under one condition if there exists such path.

step 2:

since the patch contains every edge in the graph it is obvious that every edge includes vk

step 3:

since the path includes all the edges of the graph, this means that the traverse is back at where it started, this means vk= v0

step 4:

if the longest cycle is not Eulerian then there must be an edge which is not visited.

This proves that we have an edge whose degree is even. and it is not in the longest cycle.

step 5:

But if there are two edges with the even degree then this is a contradiction and the path which we are considering is indeed a longest path cycle.

which proves that all the edges are visited and the graph has the eulirian cycle.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.