IB Maths AI 3.11 Notes

Graph theory

Graph theory is the study of networks made up of points and connections. It is used to represent many real-world systems such as road maps, transport networks, electrical circuits, and communication systems. In graph theory, the points are called vertices and the connections between them are called edges.

There are a few terms you need to be aware of:

• A graph consists of a set of vertices and a set of edges joining pairs of vertices.
• A vertex is a point in the graph. An edge is a connection between two vertices.
• Two vertices are adjacent if they are joined by an edge.
• Two edges are adjacent if they share a common vertex.
• The degree of a vertex is the number of edges connected to it.

For example, if a vertex is joined to $3$ edges, then its degree is $3$.

Consider a graph with vertices $A$, $B$, $C$, and $D$, and edges $AB$, $AC$, $BC$, and $CD$. State the adjacent vertices of $A$, and the degrees of $A$ and $C$.

• The adjacent vertices to $A$ are $B$ and $C$.
• The degree of $A$ is $2$.
• The degree of $C$ is $3$, because it is connected to $A$, $B$, and $D$.