COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

Tutorial 9: Graph Theory

Graph Fundamentals

Concept(s)

A graph G is a pair (V, E) where V is the set of vertices and E is the set of edges.
Undirected Graph: Every edge e ∈ E has the form {x, y}, where x, y ∈ V and x 6= y.
Directed Graph: Every edge e ∈ E has the form (x, y), where x, y ∈ V .
We can represent a graph with a
• Picture: Vertices as dots and edges as lines or arrows between dots
• Adjacency Matrix: An n × n matrix where entry (i, j) is 1 if vertices i and j are connected
• Adjacency List: For each vertex, we list its neighbouring vertices
• Incidence Matrix: Rows are vertices and columns are edges. We mark the vertices in each edge

Exercise 1. Consider the undirected graph G with

V = {a, b, c, d, e},

E = {a, b}, {b, c}, {c, d}, {b, d} .

a) Draw the graph G pictorally.

b) Represent the graph G as an adjacency matrix.
c) Represent the graph G as an adjacency list.
d) Represent the graph G as an incidence matrix.
Exercise 2. Consider the directed graph G with

V = {a, b, c},
E = {(a, b), (a, c), (c, b), (b, c), (a, a)}.

a) Draw the graph G pictorally.

b) Represent the graph G as an adjacency matrix.
c) Represent the graph G as an adjacency list.
d) Represent the graph G as an incidence matrix.

Concept(s)

For undirected graphs: The degree of a vertex v, deg(v), is the number of edges attached to v.
X
deg(v) = 2 · |E|
v∈V

For directed graphs:

The in-degree of a vertex v, indeg(v), is the number of edges going into v.

Tutorial 9, 2024 Term 3 1 Graph Theory

COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

The out-degree of a vertex v, outdeg(v), is the number of edges going out of v.

X X
indeg(v) = outdeg(v) = |E|
v∈V v∈V

Exercise 3. What is the degree of each vertex in G from Exercise 1?

Exercise 4. What is the degree of each vertex in G from Exercise 2?

Paths and Connectedness

Concept(s)

{v0 ,v1 } {v1 ,v2 } {vn−1 ,vn }

Walk: Sequence of vertices v0 −−−−−→ v1 −−−−−→ . . . −−−−−−−→ vn
Trail: A walk where no edge is repeated
Path: A walk where no vertex is repeated
Closed: The starting and ending vertices are the same
Cycle: A walk of length ≥ 3 where v0 = vn and all other vertices are distinct

Exercise 5. Consider the following graph G:

d f

a c

b e

For each sequence of vertices, determine whether it represents a walk, trail, path, closed walk, closed
trail, cycle or none of these options:
a) abcef cbd
b) abcef cd
c) abcef cdba
d) adbcf e
e) bcef cdb
f) bcdb
g) abef cd

Concept(s)

Connected (Undirected): For all u, v ∈ V , there exists a path from u to v

Strongly Connected (Directed): For all u, v ∈ V , there exists a path from u to v and from v to u
Connected Component: U ⊆ V that is connected and not a part of any larger connected set.

Tutorial 9, 2024 Term 3 2 Graph Theory

COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

Types of Graphs

Concept(s)

Tree: A connected graph that contain no cycles (acyclic). We have |V | = |E| + 1.

Complete Graph Kn : A graph where every pair of vertices share an edge. There are n
edges.


2

Bipartite Graph: A graph where the vertices can be divided into two disjoint sets. Each edge must
connect a vertex from one set the other.
Complete Bipartite Graph Km,n : A vertex in one set has an edge with every vertex in the other set.
We have m · n edges in total.

Exercise 6. On a tree, a leaf is a vertex with degree 1. Let ∆ be the maximum degree for tree T . Prove
that there are at least ∆ leaves.
Exercise 7. Explain why the following graph is bipartite. Add edges to the graph to make it complete.

Graph Isomorphism

Concept(s)

A graph isomorphism is a bijection between the vertex sets of graph G and H

φ : VG → VH

such that (x, y) ∈ EG if and only if (φ(x), φ(y)) ∈ EH .

Exercise 8. The graph G is as follows:

8
1 7

2 9 6

3 5
4

How many isomorphisms are there from G to itself?

Tutorial 9, 2024 Term 3 3 Graph Theory

COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

Eulerian and Hamiltonian Traversals

Concept(s)

Euler Trail: Trail containing every edge exactly once.

A connected graph has an Euler trail if and only if exactly 0 or 2 vertices have an odd degree
Euler Circuit: Closed Euler trail.
A connected graph has an Euler circuit if and only if all vertices have an even degree

Exercise 9. Consider the graph G:

1 2 3 4

Does this graph have an Euler trail? Does this graph have an Euler circuit?

Concept(s)

Hamilton Path: Path visiting each vertex exactly once

Hamilton Cycle: Closed Hamilton path
In general, there is no easy way to prove or disprove the existence of Hamiltonian cycles.

Exercise 10. Find a Hamiltonian cycle in the following graph G:

Is there a Hamiltonian path?

Coloring and Cliques

Tutorial 9, 2024 Term 3 4 Graph Theory

COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

Concept(s)

Coloring: Assignment c : V → [1..t] where adjacent vertices have different colors

Chromatic Number χ(G): The minimum number t to colour a graph
We find that χ(G) = |V | if and only if G = K|V | .
Odd cycles have a chromatic number of 3 and even cycles have a chromatic number of 2.

Exercise 11. Let G = (V, E) be a graph. We construct a new graph G0 by adding a vertex and connecting
it to all vertices in V . What is χ(G0 ) in terms of χ(G)?
Exercise 12. Prove that χ(G) ≤ 4 for the graph G from Exercise 10.

Concept(s)

Subgraph: A graph (V 0 , E 0 ) is a subgraph of graph (V, E), if V 0 ⊆ V and E 0 ⊆ E

Clique: A complete subgraph of G. A clique of k nodes is called a k-clique
Clique Number κ(G): Size of largest clique in graph G

χ(G) ≥ κ(G)

Exercise 13. We use the graph G from Exercise 10. Show that χ(G) ≥ 3 using the clique number. Can
you show that χ(G) ≥ 4?

Planar Graphs

Concept(s)

A graph is planar if it can be drawn in the plane with no crossing edges.

A graph is non-planar if and only if it contains a subdivision of K5 or K3,3 .

Exercise 14. Prove the following graph G is planar:

Exercise 15. Prove that the graph from Exercise 10 is non-planar.

Tutorial 9, 2024 Term 3 5 Graph Theory

COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

Extra Practice Problems

Note(s)

These practice questions are designed to help deepen your understanding. No answers will be pro-
vided, as the goal is to encourage independent problem-solving and reinforce key concepts.

1. Consider the graph G:

1

a) Represent this graph as an adjacency matrix.

b) Find all vertices with odd degree.
c) List all paths from vertex 1 to vertex 5.
d) Find all connected components.

2. Which of these graphs are isomorphic? Justify your answer.

Graph 1 Graph 2 Graph 3

3. Consider these two bipartite graphs:

Graph A Graph B

a) Are these graphs isomorphic?

b) Find a Hamilton cycle in each graph (if one exists).
c) Find an Euler trail in each graph (if one exists).
d) What is the chromatic number of each graph?

Tutorial 9, 2024 Term 3 6 Graph Theory

COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

4. For the following graph:

a) Find its chromatic number.

b) Is it planar? Justify your answer.
c) List all cycles of length 4.
d) What is the minimum number of edges that must be added to make it Hamiltonian?

5. Let G be a graph with n vertices. For each statement, find the smallest value of n where it becomes
possible:
a) G is planar and has exactly 12 edges
b) G has exactly 4 vertices of degree 3 and all other vertices have degree 2
c) G is bipartite and has exactly 8 edges
d) G has exactly 3 different Hamilton cycles

6. A graph G has chromatic number 4. Justify which of the below statements are correct:
a) G must contain K4 as a subgraph
b) G must be non-planar
c) Removing any vertex from G must result in a graph with chromatic number at least 3
d) G must have at least 7 edges

7. Consider the following graph G:

a) Find the chromatic number of G.

b) Is G isomorphic to K3,3 ?
c) Does G have a Hamilton cycle?
d) Does G have an Euler circuit?

8. Find a complete bipartite graph Km,n that is isomorphic to each of these graphs:

Tutorial 9, 2024 Term 3 7 Graph Theory

COMP9020 Foundations of Computer Science Hao Ren, Ronald Chiang, Varun Agarwal

Graph A Graph B

9. For the following graph:

a) Find all 5-cycles.

b) What is the size of the largest clique?
c) Find a proper coloring using the minimum number of colors.
d) Is this graph planar? If yes, draw it without crossing edges.

Tutorial 9, 2024 Term 3 8 Graph Theory