discrete structures

Problem 1. (10 points) 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 vovi ...vk 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 Vk. Step 3. Prove that vk- Vo. 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 (x, v) that is not on the longest cycle while vi is on the longest cycle. Step 5. Now construct a path that is longer than the longest path to arrive at a contradicton. Problem 1. (10 points) 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 vovi ...vk 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 Vk. Step 3. Prove that vk- Vo. 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 (x, v) that is not on the longest cycle while vi is on the longest cycle. Step 5. Now construct a path that is longer than the longest path to arrive at a contradicton