Graph terminology

Published by: Anil K. Panta

Graph Terminology

Graphs are among the most powerful and widely used data structures in computer science. They are used to model relationships and connections in real-life systems — from social networks to road maps, internet routing, and airline networks.

In this article, you'll learn the essential graph terminologies, both basic and advanced, with simple explanations and real-life analogies.

Importance of Graph Terminology

Understanding graph terminology is key to solving problems efficiently using graphs.

It gives a common language for discussing graph concepts.
Helps in designing and understanding graph algorithms like BFS, DFS, Dijkstra, etc.
Makes it easier to collaborate and communicate on projects involving networks, data structures, and algorithms.
Crucial for interviews, competitive programming, and real-world projects.

Basic Graph Terminology

1. Graph (G)

A Graph is a set of vertices (nodes) and a set of edges (connections) that link pairs of vertices.

Notation:
G = (V, E)
Where:

V = Set of vertices
E = Set of edges

Example: In a social network, people are vertices and their friendships are edges.

2. Vertex (or Node)

A vertex is a fundamental unit in a graph that represents an entity.

In Facebook: Each user is a vertex
In a map: Each city or location is a vertex

A graph can have labeled or unlabeled vertices.

3. Edge

An edge connects two vertices and represents a relationship or link between them.

In a directed graph, edges have a direction (one-way)
In an undirected graph, edges are bidirectional

Examples:

Twitter: Follow (directed edge)
Facebook: Friend (undirected edge)

4. Degree of a Vertex

The degree of a vertex is the number of edges connected to it.

In undirected graphs: just count the edges connected
In directed graphs:
-
- In-degree: Number of incoming edges

- Out-degree: Number of outgoing edges

Example:
In a YouTube network:

Channels followed by others = In-degree
Channels you follow = Out-degree

5. Path

A path is a sequence of vertices where each pair is connected by an edge.

It shows a route or connection from one node to another
A simple path doesn’t repeat vertices
A shortest path has the minimum number of steps (or weight)

Example:
In Google Maps, the route from your home to your school is a path.

6. Cycle

A cycle is a path that starts and ends at the same vertex without repeating other nodes.

Used to detect loops in graphs
Important in circuit design, deadlock detection, and graph traversal

Example:
A team of three people sending emails in a loop: A → B → C → A is a cycle.

Applications of Graphs

Graphs are used everywhere! Here are just a few real-world applications:

Application Area	Description
Social Networks	Represent users and friendships/followers
Navigation Systems	Roads, locations, shortest paths
Computer Networks	Routers and their connections
Search Engines	Linking between web pages (PageRank uses graphs)
Game Development	Pathfinding in game maps (AI logic)
Project Scheduling	Task dependencies using DAGs (Directed Acyclic Graphs)

Final Summary

Term	Definition
Graph	A set of nodes and edges representing relationships
Vertex	A point or node in the graph
Edge	A line connecting two vertices
Degree	Number of edges at a vertex (in-degree / out-degree in directed)
Path	A route between nodes
Cycle	A closed path that starts and ends at the same vertex

Final Thought:

Learning graph terminology is the first step toward mastering graph algorithms. Whether you're analyzing social media, maps, or networks, graphs give you the power to represent and solve real-world problems.