MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 36 – Matrix Representations of Graphs, Trees.
𝑣𝑣𝑣𝑣 𝑒5 𝑒𝑒𝑒𝑒𝑒 1234 12345
𝑣1 0 1 0 1 𝑣1 0 0 1 1 0
𝐴=𝑣2 1020 𝑁=𝑣2 11100
𝑣3 0 2 0 0 𝑣3 1 1 0 0 0
𝑣1001 𝑣00012 44
Exam revision sessions: Mon 1 Nov 12-1:30pm
Fri 5 Nov 1-2:30pm
Room 7-222 and on Zoom
The mathematics first year learning centre will operate 2-4pm each weekday afternoon until 12 Nov: Room 67-443
and via Zoom.
Learning Goals
Learn how to represent a graph by an adjacency matrix. Learn how to represent a graph by an incidence matrix. Learn how to draw a graph from its adjacency matrix. Learn how to draw a graph from its incidence matrix. Understand the properties of trees.
Student questions and comments:
Incidence matrix – How do you remember which of vertices/edges is the rows and which the columns? Is it ok to swap them?
There are 11 (essentially) different trees with 7 vertices.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 36 – Matrix Representations of Graphs, Trees.
Adjacency matrices for graphs:
The adjacency matrix for a graph with vertices
𝑣1 0 1 0 1 matrix𝐴=𝑣21021
𝑣 , 𝑣 , … , 𝑣 is the 𝑛 × 𝑛 matrix 𝐴 = [𝑎 ] where each 12 𝑛 𝑖𝑗
is the number of edges with endpoints
Activity 1: Write down the adjacency matrix for the graph on the right.
𝑣𝑣𝑣𝑣𝑣 12345
𝑣3 00010 𝑣
Activity 2: Draw the graph for the adjacency matrix on the left.
430101 𝑣5 12010
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 36 – Matrix Representations of Graphs, Trees.
Question 1:
Which of the following is an adjacency matrix for a graph?
1022 D. 0 2 0 0 1101
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Incidence matrices for graphs:
Lecture 36 – Matrix Representations of Graphs, Trees.
The incidence matrix for a graph with vertices
𝑣 , 𝑣 , … , 𝑣 and edges 𝑒 , 𝑒 , … , 𝑒 is the 𝑛 × 𝑚
1 2 𝑛 1 2 𝑚
matrix 𝑁 = [𝑛𝑖𝑗] where each entry 𝑛𝑖𝑗 is the number
Incidence matrix
𝑣1 0 0 1 1 0
of times vertex 𝑣 is incident with edge 𝑒 .
2 1 1 0 0 0 𝑣3
Activity 3: Write down the incidence matrix
for the graph on the right.
𝑣1 2 1 0 0
𝑣2 0 1 0 0
𝑣5 𝑒3 𝑣2 𝑒4
Activity 4: Draw the graph for the incidence matrix on the left.
𝑣1 𝑒4 𝑣 𝑖𝑗4𝑣00012
𝑣 1 1 1 0 0
𝑣3 0 0 2 0 𝑣
4 0001 𝑣5 0 0 0 1
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
Lecture 36 – Matrix Representations of Graphs, Trees.
Question 2:
Which of the following is an incidence matrix for a graph?
0101 1022 0200 1101
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021
A trivial circuit is a circuit consisting of a single vertex and no edges. A non-trivial circuit is a circuit that has edges.
A graph is circuit-free if there are no non-trivial circuits.
Lecture 36 – Matrix Representations of Graphs, Trees.
Definition: A graph is a tree if and only if it is connected and circuit-free.
If any edge is deleted from a tree then the result is a disconnected graph.
This disconnected graph consists of two trees.
Theorem: A graph 𝐺 with 𝑛 vertices is a tree if and only if it is simple, connected and has 𝑛 − 1 edges.
The proof is by induction and the main argument is:-
So the number of edges in the original tree that had 𝑛 + 1 vertices is
𝑝−1 + 𝑞−1 +1=𝑝+𝑞−1.
Since 𝑝 + 𝑞 = 𝑛 + 1, the original tree has 𝑛 edges.
Deleting an edge from a tree with 𝑛 + 1 vertices gives two smaller trees.
Let 𝑝 and 𝑞 be the numbers of vertices in these two smaller trees. By the induction hypothesis they have 𝑝 − 1 and 𝑞 − 1 edges.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 36 – Matrix Representations of Graphs, Trees.
Handshake Theorem: The sum of the degrees of a graph is twice the number of edges.
Activity 5:
Every vertex of a tree with 15 edges has either degree 3 or degree 1. How many vertices of the tree have degree 3?
Theorem: A graph 𝐺 with 𝑛 vertices is a tree if and only if it is simple, connected and has 𝑛 − 1 edges.
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 36 – Matrix Representations of Graphs, Trees.
Activity 6:
A tree has two vertices of degree 4, one vertex of degree 2, and all the other vertices have degree 1. How many vertices does the tree have?
MATH1061/MATH7861 Discrete Mathematics Semester 2, 2021 Lecture 36 – Matrix Representations of Graphs, Trees.
Activity 7:
Prove that every tree with at least two vertices has at least two vertices of degree 1.