---
title: "Short note: Eulerian graph"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:eulerian-graph-short-note"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/eulerian-graph-short-note
site: BCT Engineering
---

# Short note: Eulerian graph

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2068 Bhadra, 4 marks; 2069 Bhadra, 3 marks (asked 2 times)
- Video: [Euler Graph in Graph Theory | Euler Path & Euler Circuit with examples](https://www.youtube.com/watch?v=FoiLXsV-bnI) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/eulerian-graph-short-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on Eulerian graph.

## Short answer

An Eulerian graph has an Euler circuit, a closed trail that uses every edge exactly once, which exists if and only if all vertices have even degree. If exactly two vertices have odd degree, the graph has an Euler path but no circuit.

## Answer

An **Euler circuit** in a graph is a closed walk that uses every edge exactly once; a graph that has one is **Eulerian**. An **Euler path** uses every edge exactly once but need not be closed (such a graph is semi-Eulerian). The idea comes from Euler's solution of the Königsberg bridge problem (1736): that graph has no Euler path because all four land areas have odd degree.

**Theorems (undirected, connected graph):**
- It has an Euler circuit if and only if every vertex has even degree.
- It has an Euler path (not a circuit) if and only if exactly two vertices have odd degree; the path starts at one and ends at the other.

**Directed graphs:** an Euler circuit exists iff the graph is connected and in-degree = out-degree for every vertex.

**Example (bowtie):**
```text
   a         d
   |\       /|
   | \     / |
   |  \   /  |
   |   \ /   |
   |    c    |
   |   / \   |
   |  /   \  |
   | /     \ |
   b         e
```
Edges: ab, ac, bc, cd, ce, de. Degrees: c = 4, all others 2. Every degree is even, so an Euler circuit exists: c → a → b → c → d → e → c.

Methods: Fleury's algorithm (do not cross a bridge unless forced) or Hierholzer's algorithm. Applications: route planning for mail delivery, snow-plowing and garbage collection.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. A connected undirected graph has an Euler circuit iff:
   A. Exactly two vertices have odd degree
   B. It has no cycles
   C. Every vertex has even degree
   D. Every vertex has degree 2
   Answer: C. Closed walks pair up edges at each vertex. (Key point: Circuit condition)

2. A connected graph has an Euler path (not a circuit) iff:
   A. All vertices have even degree
   B. Exactly one vertex has odd degree
   C. All vertices have odd degree
   D. Exactly two vertices have odd degree
   Answer: D. The path starts at one odd vertex and ends at the other. (Key point: Path condition)

3. Why did the Konigsberg bridge problem have no Euler path?
   A. All four land areas had odd degree
   B. It had too few bridges
   C. It was disconnected
   D. All areas had even degree
   Answer: A. More than two odd vertices rules out both circuit and path. (Key point: Konigsberg)

4. A directed connected graph has an Euler circuit iff:
   A. Every degree is even
   B. In-degree equals out-degree at every vertex
   C. Total in-degree is 0
   D. It has no cycles
   Answer: B. Each entry to a vertex must be matched by an exit. (Key point: Directed graphs)