IB Mathematics AI AHL Graph theory Graphs, vertices, edges MAI Study Notes- New Syllabus

IB Mathematics AI AHL Graph theory Graphs, vertices, edges MAI Study Notes

LEARNING OBJECTIVE

Graph theory

Key Concepts:

Introduction to Graph Theory
Minimum Spanning Trees

Graph:

A graph is a mathematical structure used to represent relationships between objects, consisting of vertices (also known as nodes) and edges that connect pairs of vertices. In simpler terms, a graph is like a network of interconnected points (vertices) joined by lines (edges).

A graph G [or a graph $G(V,E)$] consists of:

a set of vertices V
a set of edges between vertices E

For example, the graph G with:

$V=\{A,B,C,D,E\}$
$E=\{AB,AE,BC,BE, CD, CE, DE\}$ is the following:

The vertices A and B are adjacent (they are linked by edge AB).
The edges AB and BC are adjacent (they are linked by vertex B).
A and C are not adjacent. AB and EC are not adjacent.

Graph is simple if

It contains no loops (e.g. edge A to itself)
It contains no parallel edges (e.g., two edges from A to B)

Adjacency:

Two vertices are considered adjacent if they are directly connected by an edge.
Two edges are considered adjacent if they share a common vertex.

Degree of a Vertex: The degree of a vertex is the total number of edges connected to it. Equivalently, it’s the number of vertices adjacent to that vertex.

For each vertex we define:
$\text{degree of A = number of adjacent vertices}$

Example

Find Out Number of Vertex and Degree in given graph.

▶️Answer/Explanation

Solution:

Simple Graphs: A graph is called simple if it meets two conditions:

1. It has no loops (an edge connecting a vertex to itself).
2. It has no parallel edges (more than one edge connecting the same pair of vertices).

Relationships like friendship between different people are often modeled using simple graphs.

Complete Graphs:

A complete graph is a simple graph where every distinct pair of vertices is connected by an edge. A complete graph with $n$ vertices is denoted as $K_n$. It contains the maximum possible number of edges for a simple graph with $n$ vertices, which is $ \frac{n(n-1)}{2} $.

Example

How many edges does $K_5$ have?

▶️Answer/Explanation

Solution:

Look at $K_s$.
Every vertex is connected to the other 4 vertices:

$
5 \times 4=20
$

But every edge is counted twice. Thus, the total number of edges is

$
\frac{5 \times 4}{2}=10
$

In general, the complete simple graph $K_n$ contains

$
\frac{n(n-1)}{2} \text { edges }
$

Weighted Graphs:

In a weighted graph, each edge has an associated numerical value called its weight. This weight often represents a quantity like distance, cost, or capacity associated with the connection between the vertices. For example, a map showing cities (vertices) and driving distances (weights) between them can be represented as a weighted graph.

Example

we want to include the distances between 5 cities:

▶️Answer/Explanation

Solution:

The path ABCD has
length = 3 [as it contains 3 edges]
total weight = 27 [sum of weights 8+9+10=27]

Directed Graphs (Digraphs):

In a directed graph, edges have a direction associated with them, usually indicated by an arrow. An edge from vertex A to vertex B is distinct from an edge from B to A. These are useful for modeling relationships where the connection is not necessarily symmetric, like one-way streets or “following” relationships on social media.

Example

Find out relation between all the vertex .

▶️Answer/Explanation

Solution:

$A$ “follows” $B$ but $B$ “does not follow” $A$.
$E$ and C” follow” each other!
There is no relation between $A$ and $C$, etc.
Finally, the person $A$
follows 1 person: we say that the vertex $A$ has out-degree 1, has 1 follower: we say that the vertex $A$ has in-degree 1.
Similarly, $E$ (which seems to be the most “sociable” person), has out-degree 4 and in-degree 2 .

Concepts for Directed Graphs

In-Degree and Out-Degree: For a vertex in a directed graph:
The in-degree is the number of edges pointing towards that vertex.
The out-degree is the number of edges pointing away from that vertex.

Graph Structures

Subgraphs:

A subgraph is a graph formed by taking a subset of the vertices and a subset of the edges (connecting those vertices) from a larger graph.

is a simple graph of 5 vertices and 7 edges.
It is a subgraph of $K_5$

Example

Draw Two Subgraph of following graph.

▶️Answer/Explanation

Solution:

Trees:

A tree is a specific type of graph characterized by being connected and having no cycles. Key properties of a tree with $n$ vertices include:

1. It is connected (there is a path between any two vertices).
2. It contains no cycles.
3. It has exactly n-1 edges.

If a graph satisfies any two of these three properties, it must also satisfy the third and is therefore a tree. Trees represent the most minimal way to connect a set of vertices. Adding any edge to a tree creates a cycle, while removing any edge disconnects it.

For 1 vertex, there is only 1 trivial tree:

For 2 vertices, there is only 1 tree:

For 3 vertices, there are 3 trees:

Example

Given below two graph , identify which is tree and which is not. Also explain the reason.

▶️Answer/Explanation

Solution:

1. Diagram 1 is a tree because:

It is a connected graph: every node is reachable from the root node a.
There are no cycles (no way to loop back to a node you’ve already visited).
It satisfies the definition of a tree in graph theory:
A tree is an acyclic connected graph with n nodes and (n−1) edges.

Diagram 2 is NOT a tree because:

It contains cycles:
- For example: a → b → d → a is a cycle.
- Another cycle: a → c → d → a
In a tree, there should be only one unique path between any two vertices.
- Here, there are multiple paths between some vertices (e.g., from a to d)
It violates the acyclic property of a tree.

SPANNING TREE:

A spanning tree in graph theory is a subgraph of a connected, undirected graph that includes all of the vertices of the original graph and forms a tree with the minimum number of edges. It connects all vertices without creating any cycles or loops .