Exercise · ZW-EULERIAN-CYCLE-009 · ★★★ Advanced
From \(K_5\) the 4 edges of a cycle \(1\text{-}2\text{-}3\text{-}4\text{-}1\) are removed. What graph remains?
Choose one option.
Show answer
- B. It is Eulerian and has 6 edges
Explanation
There remain \(10-4=6\) edges. Vertices 1 to 4 drop from degree 4 to 2, vertex 5 keeps degree 4, and the graph stays connected (5 is adjacent to all). All degrees are even.
Review the concept: Eulerian cycle
An Eulerian cycle of a graph \(G=(V,E)\) is a cycle that traverses every edge of \(G\) exactly once.
\[G\text{ connected and }\deg(v)\text{ even }\forall v\in V\iff\text{Eulerian cycle exists}\]
More practice problems: eulerian cycle
- ZW-EULERIAN-CYCLE-001 Which of these graphs has an Eulerian cycle?
- ZW-EULERIAN-CYCLE-002 A connected graph has vertex degrees 2,4,4,6. Does it have an Eulerian cycle?
- ZW-EULERIAN-CYCLE-003 K_7 has an Eulerian cycle. How many edges does it traverse?
- ZW-EULERIAN-CYCLE-004 Which of these complete bipartite graphs has an Eulerian cycle?
- ZW-EULERIAN-CYCLE-005 A connected graph has exactly two vertices of odd degree. Which statement is true?
- ZW-EULERIAN-CYCLE-006 A connected graph has six vertices with degrees 2,2,2,2,4,x. Which value of x allows an Eulerian cy…
- ZW-EULERIAN-CYCLE-007 If a graph has an Eulerian cycle, which statement is always true?
- ZW-EULERIAN-CYCLE-008 The Königsberg bridges graph has vertices of degrees 3,3,3,5. Why is there no Eulerian cycle?