9780023606922, Chapter 2 5, Problem 69E

Prévia do material em texto

Chapter 2.5, Problem 69E Step-by-step solution Step 1 of 1 Finding an Euler Cycle in a Graph 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. Consider the following graph K5 2 1 3 5 4 Since, a graph is connected graph and each vertex is of even degree if and only if the graph has an Euler cycle. And the number of edges incident on vertex V of an undirected graph is called the degree of vertex V. Since each edge in the form of contributes twice. The degree of a vertex V is denoted by deg(v). The degrees of vertices are (vertex -> degree): Therefore every vertex in the graph K5 has a degree of 4 which is an even number. So, this graph can contain at least an Euler cycle. Consider the path It covers all the edges only once, and the same vertex have the beginning and ending of the path. Hence, the graph K5 has an Euler cycle