Given the following graphs : Which of the following is correct ?
2016
Given the following graphs :
Which of the following is correct ?
- A.
G1 contains Euler circuit and G2 does not contain Euler circuit.
- B.
G1 does not contain Euler circuit and G2 contains Euler circuit.
- C.
Both G1 and G2 do not contain Euler circuit.
- D.
Both G1 and G2 contain Euler circuit.
Attempted by 144 students.
Show answer & explanation
Correct answer: C
Key idea: A connected graph has an Euler circuit precisely when every vertex has even degree.
First graph (G1):
Vertex degrees: a = 2, b = 3, c = 2, d = 2, e = 3.
There are exactly two vertices with odd degree (b and e). Since not all vertices are even, G1 does not have an Euler circuit.
Second graph (G2):
Interpreting the diagonal intersection as a vertex e, vertex degrees are: a = 3, b = 3, c = 3, d = 3, e = 4.
There are four vertices with odd degree (the four corners). Since not all vertices are even, G2 does not have an Euler circuit.
Conclusion: Neither graph contains an Euler circuit.
A video solution is available for this question — log in and enroll to watch it.