Skip to content
Home » Plane and connected graphs

Plane and connected graphs

Here is a simple, clear, and exam-oriented explanation of Plane Graphs and Connected Graphs — important topics in Graph Theory for BCA/MCA/Engineering students.

⭐ PLANE GRAPHS AND CONNECTED GRAPHS

Graph Theory divides graphs not only by their edges and vertices, but also by how they can be drawn and how connected or “linked” they are.
Two such concepts are:

✔ Plane Graphs
✔ Connected Graphs

Let’s discuss both in detail.

⭐ PART 1: PLANE GRAPHS

A plane graph is a special drawing of a planar graph.

✔ Definition

A Plane Graph is a graph drawn in the plane such that:

  • No two edges cross each other, except at their common vertex.
  • The drawing clearly shows faces (regions), including the outer infinite face.

So:

A plane graph is a planar graph with a particular crossing-free drawing.

⭐ Planar vs Plane Graph

ConceptMeaning
Planar GraphA graph that can be drawn without edge crossings.
Plane GraphA specific drawing of a planar graph without crossings.

Every plane graph is planar,
but a planar graph becomes a plane graph only after drawing it without crossings.

⭐ Example of Plane Graph

A triangle drawn as:

A ----- B
 \     /
   \ /
    C

This is a plane graph (no crossing).

⭐ Properties of Plane Graphs

✔ Faces (Regions)

A plane graph divides the plane into connected regions, including:

  • inner faces (bounded regions)
  • outer face (unbounded region outside the graph)

✔ Euler’s Formula (Important!)

For any connected plane graph:

[
V – E + F = 2
]

Where:
V = number of vertices
E = number of edges
F = number of faces

This is extremely important in exams for proving planar graph properties.

✔ Maximum edges in planar graphs

For simple connected planar graphs:

[
E \le 3V – 6
]

For bipartite planar graphs:

[
E \le 2V – 4
]

⭐ PART 2: CONNECTED GRAPHS

A connected graph shows how well the vertices are linked.

✔ Definition

A graph is connected if:

There is a path between every pair of vertices.

Meaning:
You can travel from any vertex to any other vertex through edges.

⭐ Disconnected Graph

If even one pair of vertices is not connected by any path →
The graph is disconnected.

A disconnected graph has components (separate subgraphs where each part is connected).

⭐ Types of Connectivity

1. Vertex Connectivity (κ(G))

Minimum number of vertices whose removal makes the graph disconnected.

Example:

  • For a tree → κ(G) = 1
  • For complete graph (K_n) → κ(G) = n−1

2. Edge Connectivity (λ(G))

Minimum number of edges whose removal disconnects the graph.

Example:

  • Tree → λ(G) = 1
  • Cycle (C_n) → λ(G) = 2
  • Complete graph (K_n) → λ(G) = n−1

3. Connected Graph (Undirected)

All vertices reachable from each other.

4. Strongly & Weakly Connected (Directed Graphs)

✔ Strongly Connected

For all vertices u, v:
u → v and v → u (directed paths).

✔ Weakly Connected

If ignoring direction makes the graph connected.

⭐ Examples

✔ Connected Graph

A — B — C — D
All vertices connected.

✔ Disconnected Graph

A — B C — D
Two disconnected components.

⭐ Relation Between Plane and Connected Graphs

Plane Graph: property about how graph is drawn
Connected Graph: property about relationship between vertices

A graph can be:

  • Plane and connected
  • Plane but disconnected
  • Connected but not planar
  • Both planar and non-planar

Example:

  • Trees → always planar and always connected.
  • Complete graph K₅ → not planar but connected.
  • Two triangles not touching → planar but disconnected.

⭐ Applications

✔ Plane Graphs

  • Circuit board design
  • Geographical maps
  • Visualization of networks
  • Computer graphics

✔ Connected Graphs

  • Transportation networks
  • Communication networks
  • Routing algorithms
  • Social networks
  • AI and robotics (path finding)

⭐ Quick Exam-Oriented Summary

Plane Graph

A planar graph drawn with no crossing edges.
Shows faces and satisfies Euler’s formula:
[
V – E + F = 2
]

Planar Graph Edge Limits

Simple graph: (E \le 3V – 6)
Bipartite: (E \le 2V – 4)

Connected Graph

Every two vertices have a path.
Components = maximal connected subgraphs.

Connectivity Measures

  • Vertex connectivity κ(G)
  • Edge connectivity λ(G)
  • Strong/weak connectivity for digraphs