Unit 14: Introduction to Graph Theory

1. Definition of Graphs, Vertices, and Edges
2. Types of Graphs
3. Degree of a Vertex
4. Paths and Connectivity
5. Introduction to Trees
6. Exam Focus Enhancements

1. Definition of Graphs, Vertices, and Edges

A Graph (G) is a mathematical structure consisting of two sets: a set of Vertices (V) (also called nodes) and a set of Edges (E) that connect pairs of vertices.

Formal Notation: G = (V, E).
Example: V = \{v₁, v₂, v₃\}, E = \{(v₁, v₂), (v₂, v₃)\}.

2. Types of Graphs

Graphs are classified based on the nature of their edges and connections:

Type	Description
Undirected Graph	Edges have no direction (connection is two-way).
Directed Graph (Digraph)	Edges have a specific direction (represented by arrows).
Simple Graph	A graph with no self-loops and no multiple edges between the same vertices.
Complete Graph (K_n)	A graph where every vertex is connected to every other vertex exactly once.

3. Degree of a Vertex

The Degree of a vertex is the number of edges incident (connected) to it. For directed graphs, we distinguish between In-degree (arrows coming in) and Out-degree (arrows going out).

Handshaking Lemma: The sum of the degrees of all vertices in a graph is twice the number of edges.
∑ deg(v) = 2 × |E|

4. Paths and Connectivity

Path: A sequence of edges that allows you to travel from one vertex to another.
Cycle: A path that starts and ends at the same vertex without repeating edges or vertices (except the start/end).
Connected Graph: A graph where there is a path between every pair of vertices.

5. Introduction to Trees

A Tree is a special type of connected graph that has no cycles. Trees are fundamental in computer science for organizing data (like folder structures or HTML DOM).

Properties of a Tree:

If a tree has n vertices, it must have exactly n-1 edges.
There is exactly one unique path between any two vertices.
Adding any one edge to a tree creates exactly one cycle.

6. Exam Focus Enhancements

Exam Tips

Degree Calculation: In a simple graph, a self-loop (if allowed in a multigraph) counts as two degrees for that vertex.
The n-1 Rule: If an exam question asks if a connected graph with 10 vertices and 10 edges is a tree, the answer is No (it must have 9 edges).
Handshaking Application: Use the Handshaking Lemma to find the number of edges if the degrees of all vertices are given.

Common Mistakes

Directed vs Undirected: Forgetting to use arrows when drawing a directed graph. In directed graphs, (v₁, v₂) is NOT the same as (v₂, v₁).
Simple Graph Rules: Including multiple edges between two vertices when asked to draw a *simple* graph.
Disconnected Trees: Thinking a tree can be disconnected. A disconnected graph without cycles is called a **Forest**.

Frequently Asked Questions

Q: What is an Isolated Vertex?
A: A vertex with a degree of 0 (no connections).

Q: What is a Pendant Vertex?
A: A vertex with a degree of 1 (a "leaf" in a tree).

Q: Why is Graph Theory important for BCA?
A: It is used in networking (topology), database management (relationships), and algorithm design (pathfinding).