1,401 views

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 ans returns to the vertex after tracelling 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 \}.$$

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

### 1 comment

$E(G) = \{ \{i, j\} : 1 \leq i < j \leq 5 \: or \: 5 \leq i < j \leq 9 \}.$

• $\text{Total} = \binom{9}{2} \;\;\;\; \text{\{i,j\}} \text { pairs possible}.$
• Because of this condition $\left ( 1 \leq i < j \leq 5 \: \right ) or \: \left ( 5 \leq i < j \leq 9 \right )$ only 20 of them are valid and shown above.