What is a Graph? (VCE SSCE General Mathematics): Revision Notes
What is a Graph?
Introduction
In everyday life, we encounter many situations involving connections between people or objects. Towns link together through roads, computers connect to the internet, and people form friendships on social media platforms. A graph is a mathematical diagram that represents these connections visually.
Graphs are powerful tools for modeling real-world networks and relationships. They help us understand complex systems by simplifying them into points (vertices) and connections (edges). From analyzing social networks to planning transportation routes, graphs have countless practical applications in our daily lives.
Understanding graph elements
Graphs, vertices and edges
A graph is a diagram made up of points called vertices (the plural of vertex) that are connected by lines called edges.
Think of vertices as the objects or people in a network, and edges as the connections or relationships between them.
Social Media Connections
In this graph showing social media friendships:
- The vertices represent people: Anna, Brett, Cara, Dario and Ethan
- The edges represent the friendship connections between them
- We can see that:
- Anna is friends with Brett and Cara
- Brett is friends with Anna, Cara, Dario and Ethan
- Cara is friends with Anna, Brett and Dario
- Dario is friends with Brett and Cara
- Ethan is friends with Brett
Special features of graphs
Graphs can have special features that are important to recognise:
Loops
A loop is an edge that connects a vertex to itself. It forms a circle starting and ending at the same point.
Multiple edges
When two or more edges connect the same pair of vertices, these are called multiple edges. They show repeated connections between the same two points.
These special features—loops and multiple edges—can significantly affect the properties of a graph. Always check for them when analyzing a graph, as they require special attention when counting degrees and edges.
Degree of a vertex
The degree of a vertex tells us how many edges are connected to that vertex. We can think of it as counting how many connections that point has.
The degree of a vertex is written using the notation: .
Calculating degrees
To find the degree of a vertex, count all the edges attached to it. However, there's an important special rule to remember:
Critical Rule for Loops:
A loop contributes two degrees to a vertex because it is attached to its vertex at both ends.
Finding Vertex Degrees
For a simple graph with vertices , , and :
- means vertex has edges connected to it
- means vertex has edges connected to it
- means vertex has edges connected to it
- means vertex has edges connected to it
Even and odd vertices
We classify vertices based on their degree:
- A vertex is even if its degree is an even number
- A vertex is odd if its degree is an odd number
This classification of vertices as even or odd becomes particularly important in more advanced graph theory topics, such as determining whether a graph has an Eulerian path or circuit.
Sum of degrees
There is an important relationship between the degrees of vertices and the number of edges in a graph:
The Fundamental Degree-Edge Relationship:
In any graph, the sum of degrees of all vertices equals twice the number of edges.
This rule works because each edge connects two vertices, so it contributes to the degree of each vertex it touches (adding to the total sum of degrees).
Note: When counting edges, remember that a loop counts as one edge.
Example: Analysing a graph
Consider this graph with vertices , and :
- There are vertices
- There are edges
- Vertex has a loop
- There are multiple edges between vertices and
Calculating Degrees and Verifying the Sum
Step 1: Calculate the degree of each vertex
- (one loop contributing degrees, plus one edge to )
- (one edge to , plus two edges to )
- (two edges to )
Step 2: Find the sum of degrees
Step 3: Calculate twice the number of edges
Step 4: Verify the relationship
✓
This confirms our rule: the sum of degrees equals twice the number of edges.
Worked example
Worked Example: Analyzing a Complete Graph
Question: Consider the graph shown below.
a) How many vertices does this graph have?
Solution: Vertices are the points that make up a graph. Counting the points , and :
There are vertices.
b) How many edges does this graph have?
Solution: Edges are the lines that connect the points. Counting all the lines, and remembering that a loop counts as one edge:
There are edges.
c) What is the degree of vertex ?
Solution: The degree of a vertex is the number of edges attached to it. Counting the edges connected to vertex :
d) What is the degree of vertex ?
Solution: Vertex has:
- One edge connected to vertex
- One edge connected to vertex
- One loop
Remember that a loop contributes two degrees to a vertex:
e) What is the sum of degrees for this graph?
Solution: The sum of degrees equals twice the number of edges. Since this graph has edges:
We can verify this by adding the individual degrees:
✓
Key Points to Remember:
- A graph consists of vertices (points) connected by edges (lines)
- A loop is an edge that connects a vertex to itself and contributes two degrees to that vertex
- The degree of a vertex is the number of edges attached to it, written as
- Sum of degrees always equals twice the number of edges:
- Vertices can be classified as even (even degree) or odd (odd degree)