edited by
2,198 views
7 votes
7 votes

Which of the following graphs DOES NOT have an Eulerian circuit? (Recall that an Eulerian circuit in an undirected graph is a walk in the graph that starts at a vertex and returns to the vertex after traveling on each edge exactly once.)

  1. $K_{9, 9}$
  2. $K_{8, 8}$
  3. $K_{12, 12}$
  4. $K_9$
  5. The graph $G$ on vertex set $\{1, 2, \dots , 9\}$ with edge set $$ E(G) = \{ \{i, j\} : 1 \leq i < j \leq 5 \: or \: 5 \leq i < j \leq 9 \}.$$
edited by

1 Answer

Best answer
8 votes
8 votes

A connected undirected multi graph has Euler's circuit iff all vertices are of Even degree

1.K9,9 is Bipartite graph with each side having 9 vertices and each of the vertex on one side are connected to all vertices of other side,hence degree of all vertices are 9 which is odd degree, Therefore No Eulers Circuit

2 &3 .K8,8 and K12,12 is Bipartite graph with each side having 8 vertices and each of them are connected to all vertices of other side,hence degree of all vertices are 8 and 12 respectively which is Even, Therefore Eulers Circuit exists

4. K9 Complete graph with 9 vertices with each vertex connected to all other therefore degree is 8,Therefore Eulers Circuit exists

5.

 

In this graph also all vertices have even degree. So, Euler circuit exists.

Hence Option A doesn't have Euler's circuit

edited by
Answer:

Related questions