---
title: "Short note: Planar and regular graphs"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:planar-and-regular-graphs-note"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/planar-and-regular-graphs-note
site: BCT Engineering
---

# Short note: Planar and regular graphs

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2069 Bhadra, 3 marks
- Video: [Graph Theory: 57. Planar Graphs](https://www.youtube.com/watch?v=wnYtITkWAYA) — Sarada Herke
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/planar-and-regular-graphs-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on planar and regular graphs.

## Short answer

A planar graph can be drawn without edge crossings; for connected planar graphs, v - e + f = 2 and e ≤ 3v - 6 (if v≥3). A regular graph has all vertices of the same degree k; it has nk/2 edges, so nk must be even. K_4 is both planar and 3-regular.

## Answer

#### Planar graph
A graph that can be drawn in the plane with no edges crossing. For a connected planar graph, **Euler's formula** holds: v − e + f = 2, and for a simple connected planar graph with v ≥ 3, e ≤ 3v − 6. A graph is planar iff it has no subdivision of K₅ or K₃,₃ (Kuratowski). Examples: trees, cycles and K₄ are planar, while K₅ and K₃,₃ are not.

```text
          a
         / \
        /   \
       /  d  \       d lies inside triangle abc and
      / /   \ \      is joined to a, b and c
     b --------- c
```
(K₄ drawn with no crossing.)

#### Regular graph
A graph in which every vertex has the same degree k (a k-regular graph). On n vertices it has nk/2 edges, so nk must be even. Examples: Cₙ is 2-regular, Kₙ is (n − 1)-regular, and the cube Q₃ is 3-regular.

Both: K₄ and the cube Q₃ are regular and planar. K₅ is regular but not planar.

## Check yourself

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

1. For a connected planar graph:
   A. v - e + f = 2
   B. v + e + f = 2
   C. v - e = f
   D. e = 2v
   Answer: A. This holds for any connected planar embedding. (Key point: Euler's formula)

2. A k-regular graph on n vertices has:
   A. nk edges
   B. nk/2 edges, so nk is even
   C. n + k edges
   D. 2nk edges
   Answer: B. Degree sum nk = 2e. (Key point: Regular edges)

3. Which graph is regular but not planar?
   A. K4
   B. Q3
   C. K5
   D. C5
   Answer: C. K5 is 4-regular but violates e <= 3v - 6. K4 and Q3 are regular and planar. (Key point: Both properties)