9780023606922, Chapter 2 5, Problem 72E

Prévia do material em texto

Chapter 2.5, Problem 72E Step-by-step solution Step 1 of 1 Euler Cycle in a Graph Complete Graph: A simple graph with " vertices is called a complete graph if there is an edge between each pair of different vertices, and it denoted by Euler Cycle: If a cycle of a graph G contains every edge in the graph G only once, and contains every vertex in the graph G and the beginning and ending vertices are the same, then the cycle is called as Euler cycle of the graph G. Since, a graph is connected graph and each vertex is of even degree if and only if the graph has an Euler cycle. When n=1, an Euler cycle is not possible as no edges exist to in the graph. When n=2, there is only one edge and it is repeated twice, so it does not contain an Euler cycle. When n=3, there are three edges and each vertex has even degree, so it is an Euler cycle. When n=4, there are eight edges and every vertex have an odd degree, so it does not contain an Euler cycle. And so on. So, if n is odd, then the degree of every vertex is even in the graph as each vertex is connected with even number of (n-1) vertices. So, if n is even, then the degree of every vertex is odd in the graph Ka as each vertex is connected with even number of (n-1) vertices. Hence, the graph has an Euler cycle only when n is odd.