(b) Suppose that Go is an undirected graph with an Euler tour. Also, suppose G1 is obtained by tweaking Go, G2 by tweaking GI, and so forth. Use induction to prove that every graph Gn obtainable in this way has an Euler tour For your reference An Euler tour is a closed walk that traverses every edge in a graph exactly once A graph is connected if and only if there is a path between every pair of vertices Theorem. An undirected graph has an Euler tour if and only if the graph is connected and every vertex has even degree Solution. We use induction. Let P(n)be the proposition that Gn has an Euler tour Base case. Go has an Euler tour by supposition Inductive step. For n>0, we assume Gn has an Euler Tour and prove that gn+l also has an Euler tour. Specifically, we show that Gn+1 has only even-degree vertices and is connected Every vertex in Gn has even degree, since Gn has an Euler tour. Every vertex Thus, every vertex in Gn+1 has even degree Consider arbitrary vertices u and v in Gn+1. Since Gn is connected there is a path from u to u in Gn. If the path does not contain c-d, then the same path exists in Gn+1. If the path does contain c-d, then there is a corresponding path in Gn+1 where c-d is replaced by edges c-a and a-d This implies Gn+I has an Euler tour as well. Therefore gn has an euler tour for all n> 1. In particular, G6042 has an Euler TourQuiz 1 6 (b) Suppose that G0 is an undirected graph with an Euler tour. Also, suppose G1 is obtained by tweaking G0, G2 by tweaking G1, and so forth. Use induction to prove that every graph Gn obtainable in this way has an Euler tour. For your reference: • An Euler tour is a closed walk that traverses every edge in a graph exactly once. • A graph is connected if and only if there is a path between every pair of vertices. • Theorem. An undirected graph has an Euler tour if and only if the graph is connected and every vertex has even degree. Solution. We use induction. Let P(n) be the proposition that Gn has an Euler tour. Base case. G0 has an Euler tour by supposition. Inductive step. For n ≥ 0, we assume Gn has an Euler Tour and prove that Gn+1 also has an Euler tour. Specifically, we show that Gn+1 has only even-degree vertices and is connected: • Every vertex in Gn has even degree, since Gn has an Euler tour. Every vertex in Gn+1 has the same degree, except for vertex a which has degree two greater. Thus, every vertex in Gn+1 has even degree. • Consider arbitrary vertices u and v in Gn+1. Since Gn is connected, there is a path from u to v in Gn. If the path does not contain c—d, then the same path exists in Gn+1. If the path does contain c—d, then there is a corresponding path in Gn+1 where c—d is replaced by edges c—a and a—d. This implies Gn+1 has an Euler tour as well. Therefore, Gn has an Euler tour for all n ≥ 1. In particular, G6042 has an Euler Tour