1. Learn
  2. Quick Notes
  3. List
  4. Networking
Back

Network 

5.1 Network — Mathematics Form 4
MATHEMATICS • Form 4 • Chapter 5: Network in Graph Theory

5.1 Network

Graph theory is an important branch of mathematics used to model relationships between discrete objects. A graph consists of a set of dots called vertices and lines linking them called edges. A network is part of a graph where vertices and edges have specific characteristics, representing real-world systems such as transportation, computer networks, and social connections.

Learning Objectives

  • Identify and explain a network as a graph.
  • Compare and contrast directed graphs and undirected graphs, as well as weighted graphs and unweighted graphs.
  • Identify and draw subgraphs and trees.
  • Represent information in the form of networks.
  • Solve problems involving networks.

Comparison between a Loop and Multiple Edges

See how loops and multiple edges contribute to vertex degrees and how their edge pairs are written.

Multiple Edges
A B
Two distinct edges connect the same pair of vertices.
Edge pairs: \((A, B)\) and \((A, B)\)
Loop
C
An edge starts and ends at the same vertex.
Edge pair: \((C, C)\) • the loop contributes 2, so \(d(C) = 2\)

Brief Explanation

What is a Graph?

A graph is used to represent discrete objects and their relationships. It is denoted as an ordered pair \(G = (V, E)\), where \(V\) is the set of vertices and \(E\) is the set of edges linking pairs of vertices.

What is a Network?

A network is part of a graph where the vertices and edges possess their own characteristics. The data structure has a many-to-many relation.

Degree of a Vertex

The degree of a vertex is the number of edges that connect to it. The sum of degrees of a graph is twice the number of edges:

\[\sum d(v) = 2\,n(E) \quad (v \in V)\]

The sum of degrees of any graph is always an even number. A graph cannot be drawn if the sum of degrees is odd. An isolated vertex has a degree of 0 and is not connected to other vertices.

Graph type Key feature Degree rule
Simple graph No loops and no multiple edges Each edge contributes 1 to each endpoint
Multiple edges More than one edge connects the same two vertices Each edge is counted separately
Loop An edge starts and ends at the same vertex Adds 2 to the degree of that vertex
Directed graph Each edge has a direction (arrow) \(d(v) = d_{in}(v) + d_{out}(v)\)
Weighted graph Each edge has a numerical value Weight represents distance, time, cost, etc.
1
Identify the vertices
List all the dots or points in the graph as the set \(V\).
2
Identify the edges
List all the lines or arcs linking pairs of vertices as the set \(E\).
3
Check the degree sum
Verify that \(\sum d(v) = 2 \times n(E)\), which must be an even number.
4
Interpret the network
Use the graph to represent and solve real-world network problems.

Try Answering First

Read the question, answer it in your mind, then press “Check Answer”.

1

A graph has 5 vertices with degrees 2, 3, 3, 4, and 2. Can this graph be drawn? State your reason.

Answer: Yes, because the sum of degrees is \(2 + 3 + 3 + 4 + 2 = 14\), which is an even number.
2

A tree has 8 vertices. How many edges does the tree have?

Answer: A tree has \(n - 1\) edges. Therefore, the number of edges is \(8 - 1 = 7\).
3

In a directed graph, vertex \(A\) has 3 arrows pointing towards it and 2 arrows pointing away from it. What is the degree of vertex \(A\)?

Answer: The degree of vertex \(A\) is \(d(A) = d_{in}(A) + d_{out}(A) = 3 + 2 = 5\).

Subgraphs, Trees and Networks

Subgraphs and the minimum-weight tree, representing a table as a network, and solving route problems.

What is a subgraph?

A subgraph is part of a graph, or the whole graph, redrawn without changing the original positions of the vertices and edges. A graph \(H\) is a subgraph of graph \(G\) if all three conditions hold:

(a) the vertex set of \(H\) is a subset of the vertex set of \(G\), that is \(V(H) \subset V(G)\);
(b) the edge set of \(H\) is a subset of the edge set of \(G\), that is \(E(H) \subset E(G)\);
(c) the vertex pairs of the edges of \(H\) are the same as the edges of \(G\).

In short: a vertex in \(G\) is a subgraph of \(G\); an edge together with the vertices it connects is a subgraph of \(G\); and every graph is a subgraph of itself. Condition (c) matters — if a loop or an edge label is moved to a different vertex, the graph is not a subgraph.

Trees and the minimum-weight tree

A tree is a subgraph with these properties: it is a simple graph (no loops, no multiple edges); all vertices are connected and each pair of vertices is joined by exactly one path; and the number of edges \(= n - 1\) for \(n\) vertices.

For a weighted graph, the minimum-weight tree is the tree that connects every vertex with the smallest possible total weight.

20 25 10 12 17 19 14 Q R P T S

An undirected weighted graph: 5 vertices, 7 edges. Draw a tree with the minimum total weight.

1
Work out how many edges must be removed
A tree with \(n = 5\) vertices needs \(n - 1 = 4\) edges. This graph has 7 edges, so \(7 - 4 = 3\) edges must be removed.
2
Remove the heaviest edge that does not disconnect the graph
Start with the heaviest. Remove \(PQ = 25\) and \(QR = 20\). The next heaviest is \(PT = 19\), but it is the only edge still joining vertex \(P\) — removing it would leave \(P\) isolated. So keep \(PT\) and move on.
3
Remove the next heaviest edge
Remove \(RS = 17\) — vertices \(R\) and \(S\) are still connected through \(T\). Now only 4 edges remain.
4
Check and total
The remaining edges are \(QT = 10\), \(RT = 12\), \(TS = 14\) and \(PT = 19\). All 5 vertices are connected, there are exactly \(4 = 5 - 1\) edges, and there is no cycle — so it really is a tree. Minimum total weight \(= 10 + 12 + 14 + 19 = 55\).
10 12 19 14 Q R P T S

The minimum-weight tree: total weight \(= 55\).

Representing information in the form of a network

A network can be drawn as a directed or undirected graph, and as a weighted or unweighted graph. To turn a table into a network, choose one column to be the vertices and the other to be the edges.

The table below shows six pupils and the two games each one likes. Let the vertices be the types of games and the edges represent the pupils’ names. Each pupil likes exactly two games, so each pupil produces exactly one edge.

Name of pupilGames liked
EdmundBadminton, Chess
AzwanFootball, Sepak takraw
RajanChess, Football
AinaChess, Netball
MariaBadminton, Netball
JennyNetball, Volleyball
Rajan Azwan Aina Edmund Maria Jenny Chess Football Sepak takraw Netball Badminton Volleyball

The resulting network: 6 vertices (games) and 6 edges (pupils). Degrees \(= 3, 3, 2, 2, 1, 1\); sum of degrees \(= 12 = 2 \times 6\) edges.

Solving network problems: shortest and longest route

The diagram below shows the one-way paths Izarul can choose for his running practice. Vertex \(v_1\) is the starting position and \(v_5\) is the ending position. Determine (a) the shortest distance, (b) the longest distance, and (c) the vertices passed through if the run is between 1.4 km and 2.1 km.

500 600 900 500 800 500 500 v1 v3 v4 v2 v5

Every edge is one-way, in the direction of the arrow. Weights are in metres.

1
List every one-way route from \(v_1\) to \(v_5\)
Follow the arrows only. There are exactly four routes.
2
Add the weights along each route
\(v_1 \to v_2 \to v_5 = 600 + 500 = 1\,100\) m; \(v_1 \to v_3 \to v_4 \to v_5 = 500 + 500 + 500 = 1\,500\) m; \(v_1 \to v_2 \to v_4 \to v_5 = 600 + 800 + 500 = 1\,900\) m; \(v_1 \to v_2 \to v_3 \to v_4 \to v_5 = 600 + 900 + 500 + 500 = 2\,500\) m.
3
Answer
(a) Shortest \(= 1\,100\) m \(= 1.1\) km through \(v_1, v_2, v_5\). (b) Longest \(= 2\,500\) m \(= 2.5\) km through \(v_1, v_2, v_3, v_4, v_5\). (c) Between 1.4 km and 2.1 km: the 1.5 km route \((v_1, v_3, v_4, v_5)\) and the 1.9 km route \((v_1, v_2, v_4, v_5)\).

Common Mistakes

  • ! Counting a loop as degree 1 instead of degree 2. A loop adds 2 to the degree of its vertex.
  • ! Confusing the order of vertex pairs in directed graphs; writing \((A, B)\) when the arrow actually points from \(B\) to \(A\), which should be \((B, A)\).
  • ! Forgetting that every tree must be fully connected; drawing a disconnected graph with \(n - 1\) edges and mistakenly calling it a tree.
  • ! Forming closed cycles when asked to draw a tree from a graph.

Misconceptions

Misconception

Any graph with \(n(E) = n(V) - 1\) is automatically a tree.

Correct Fact

The condition \(n(E) = n(V) - 1\) is necessary but not sufficient on its own; all vertices must also be connected with no cycles or loops.

Misconception

In an undirected graph, \((u, v)\) and \((v, u)\) represent two separate edges.

Correct Fact

In an undirected graph, \((u, v)\) and \((v, u)\) represent the exact same edge. They only represent different edges in a directed graph.

Summary

  • Graph: \(G = (V, E)\) where \(V\) is the set of vertices and \(E\) is the set of edges.
  • Degree Sum Formula: \(\sum d(v) = 2 \times n(E)\), which must always be an even number.
  • Loop adds 2 to the vertex degree; multiple edges connect the same pair of vertices.
  • Directed graph: Edges have arrows; \(d(v) = d_{in}(v) + d_{out}(v)\).
  • Weighted graph: Edges carry values representing quantities like distance, cost, or time.
  • Subgraph: A subset of vertices and edges preserving original graph connections.
  • Tree: A connected simple subgraph without cycles, having \(n\) vertices and \(n - 1\) edges.

Short Activity

Complete all parts first, then press the check answer button.

A. Objective Quiz

1 Which of the following sets of vertex degrees cannot form a graph?

2 Which statement is a necessary property of a tree with \(n\) vertices?

B. Fill in the Blanks

3 If a graph has 7 edges, the sum of degrees of all its vertices is .

4 In a directed graph, the degree of a vertex \(v\) is determined by adding the number of edges entering the vertex, \(d_{in}(v)\), and the number of edges leaving the vertex, .

C. Drag and Drop: Match Each Concept to Its Description

Drag each concept to the correct description. On a phone, tap the answer choice first, then tap the description box.

Concept
Simple graph
Loop
Weighted graph
Tree
Description
A graph that has no loops and no multiple edges.CorrectTry againEmpty
An edge that starts and ends at the same vertex, adding 2 to the degree.CorrectTry againEmpty
A graph where each edge is associated with a numerical value such as distance or cost.CorrectTry againEmpty
A connected simple subgraph with \(n\) vertices and exactly \(n - 1\) edges.CorrectTry againEmpty
 

Key Terms

Vertex (bucu) Edge (tepi) Degree (darjah) Simple graph (graf mudah) Loop (gelung) Multiple edges (berbilang tepi) Directed graph (graf terarah) Undirected graph (graf tak terarah) Weighted graph (graf berpemberat) Unweighted graph (graf tak berpemberat) Subgraph (subgraf) Cycle (kitaran) Tree (pokok)
The views expressed in the notes here are those of the contributor and don’t necessarily represent the views of Pandai.

Network 

5.1 Network — Mathematics Form 4
MATHEMATICS • Form 4 • Chapter 5: Network in Graph Theory

5.1 Network

Graph theory is an important branch of mathematics used to model relationships between discrete objects. A graph consists of a set of dots called vertices and lines linking them called edges. A network is part of a graph where vertices and edges have specific characteristics, representing real-world systems such as transportation, computer networks, and social connections.

Learning Objectives

  • Identify and explain a network as a graph.
  • Compare and contrast directed graphs and undirected graphs, as well as weighted graphs and unweighted graphs.
  • Identify and draw subgraphs and trees.
  • Represent information in the form of networks.
  • Solve problems involving networks.

Comparison between a Loop and Multiple Edges

See how loops and multiple edges contribute to vertex degrees and how their edge pairs are written.

Multiple Edges
A B
Two distinct edges connect the same pair of vertices.
Edge pairs: \((A, B)\) and \((A, B)\)
Loop
C
An edge starts and ends at the same vertex.
Edge pair: \((C, C)\) • the loop contributes 2, so \(d(C) = 2\)

Brief Explanation

What is a Graph?

A graph is used to represent discrete objects and their relationships. It is denoted as an ordered pair \(G = (V, E)\), where \(V\) is the set of vertices and \(E\) is the set of edges linking pairs of vertices.

What is a Network?

A network is part of a graph where the vertices and edges possess their own characteristics. The data structure has a many-to-many relation.

Degree of a Vertex

The degree of a vertex is the number of edges that connect to it. The sum of degrees of a graph is twice the number of edges:

\[\sum d(v) = 2\,n(E) \quad (v \in V)\]

The sum of degrees of any graph is always an even number. A graph cannot be drawn if the sum of degrees is odd. An isolated vertex has a degree of 0 and is not connected to other vertices.

Graph type Key feature Degree rule
Simple graph No loops and no multiple edges Each edge contributes 1 to each endpoint
Multiple edges More than one edge connects the same two vertices Each edge is counted separately
Loop An edge starts and ends at the same vertex Adds 2 to the degree of that vertex
Directed graph Each edge has a direction (arrow) \(d(v) = d_{in}(v) + d_{out}(v)\)
Weighted graph Each edge has a numerical value Weight represents distance, time, cost, etc.
1
Identify the vertices
List all the dots or points in the graph as the set \(V\).
2
Identify the edges
List all the lines or arcs linking pairs of vertices as the set \(E\).
3
Check the degree sum
Verify that \(\sum d(v) = 2 \times n(E)\), which must be an even number.
4
Interpret the network
Use the graph to represent and solve real-world network problems.

Try Answering First

Read the question, answer it in your mind, then press “Check Answer”.

1

A graph has 5 vertices with degrees 2, 3, 3, 4, and 2. Can this graph be drawn? State your reason.

Answer: Yes, because the sum of degrees is \(2 + 3 + 3 + 4 + 2 = 14\), which is an even number.
2

A tree has 8 vertices. How many edges does the tree have?

Answer: A tree has \(n - 1\) edges. Therefore, the number of edges is \(8 - 1 = 7\).
3

In a directed graph, vertex \(A\) has 3 arrows pointing towards it and 2 arrows pointing away from it. What is the degree of vertex \(A\)?

Answer: The degree of vertex \(A\) is \(d(A) = d_{in}(A) + d_{out}(A) = 3 + 2 = 5\).

Subgraphs, Trees and Networks

Subgraphs and the minimum-weight tree, representing a table as a network, and solving route problems.

What is a subgraph?

A subgraph is part of a graph, or the whole graph, redrawn without changing the original positions of the vertices and edges. A graph \(H\) is a subgraph of graph \(G\) if all three conditions hold:

(a) the vertex set of \(H\) is a subset of the vertex set of \(G\), that is \(V(H) \subset V(G)\);
(b) the edge set of \(H\) is a subset of the edge set of \(G\), that is \(E(H) \subset E(G)\);
(c) the vertex pairs of the edges of \(H\) are the same as the edges of \(G\).

In short: a vertex in \(G\) is a subgraph of \(G\); an edge together with the vertices it connects is a subgraph of \(G\); and every graph is a subgraph of itself. Condition (c) matters — if a loop or an edge label is moved to a different vertex, the graph is not a subgraph.

Trees and the minimum-weight tree

A tree is a subgraph with these properties: it is a simple graph (no loops, no multiple edges); all vertices are connected and each pair of vertices is joined by exactly one path; and the number of edges \(= n - 1\) for \(n\) vertices.

For a weighted graph, the minimum-weight tree is the tree that connects every vertex with the smallest possible total weight.

20 25 10 12 17 19 14 Q R P T S

An undirected weighted graph: 5 vertices, 7 edges. Draw a tree with the minimum total weight.

1
Work out how many edges must be removed
A tree with \(n = 5\) vertices needs \(n - 1 = 4\) edges. This graph has 7 edges, so \(7 - 4 = 3\) edges must be removed.
2
Remove the heaviest edge that does not disconnect the graph
Start with the heaviest. Remove \(PQ = 25\) and \(QR = 20\). The next heaviest is \(PT = 19\), but it is the only edge still joining vertex \(P\) — removing it would leave \(P\) isolated. So keep \(PT\) and move on.
3
Remove the next heaviest edge
Remove \(RS = 17\) — vertices \(R\) and \(S\) are still connected through \(T\). Now only 4 edges remain.
4
Check and total
The remaining edges are \(QT = 10\), \(RT = 12\), \(TS = 14\) and \(PT = 19\). All 5 vertices are connected, there are exactly \(4 = 5 - 1\) edges, and there is no cycle — so it really is a tree. Minimum total weight \(= 10 + 12 + 14 + 19 = 55\).
10 12 19 14 Q R P T S

The minimum-weight tree: total weight \(= 55\).

Representing information in the form of a network

A network can be drawn as a directed or undirected graph, and as a weighted or unweighted graph. To turn a table into a network, choose one column to be the vertices and the other to be the edges.

The table below shows six pupils and the two games each one likes. Let the vertices be the types of games and the edges represent the pupils’ names. Each pupil likes exactly two games, so each pupil produces exactly one edge.

Name of pupilGames liked
EdmundBadminton, Chess
AzwanFootball, Sepak takraw
RajanChess, Football
AinaChess, Netball
MariaBadminton, Netball
JennyNetball, Volleyball
Rajan Azwan Aina Edmund Maria Jenny Chess Football Sepak takraw Netball Badminton Volleyball

The resulting network: 6 vertices (games) and 6 edges (pupils). Degrees \(= 3, 3, 2, 2, 1, 1\); sum of degrees \(= 12 = 2 \times 6\) edges.

Solving network problems: shortest and longest route

The diagram below shows the one-way paths Izarul can choose for his running practice. Vertex \(v_1\) is the starting position and \(v_5\) is the ending position. Determine (a) the shortest distance, (b) the longest distance, and (c) the vertices passed through if the run is between 1.4 km and 2.1 km.

500 600 900 500 800 500 500 v1 v3 v4 v2 v5

Every edge is one-way, in the direction of the arrow. Weights are in metres.

1
List every one-way route from \(v_1\) to \(v_5\)
Follow the arrows only. There are exactly four routes.
2
Add the weights along each route
\(v_1 \to v_2 \to v_5 = 600 + 500 = 1\,100\) m; \(v_1 \to v_3 \to v_4 \to v_5 = 500 + 500 + 500 = 1\,500\) m; \(v_1 \to v_2 \to v_4 \to v_5 = 600 + 800 + 500 = 1\,900\) m; \(v_1 \to v_2 \to v_3 \to v_4 \to v_5 = 600 + 900 + 500 + 500 = 2\,500\) m.
3
Answer
(a) Shortest \(= 1\,100\) m \(= 1.1\) km through \(v_1, v_2, v_5\). (b) Longest \(= 2\,500\) m \(= 2.5\) km through \(v_1, v_2, v_3, v_4, v_5\). (c) Between 1.4 km and 2.1 km: the 1.5 km route \((v_1, v_3, v_4, v_5)\) and the 1.9 km route \((v_1, v_2, v_4, v_5)\).

Common Mistakes

  • ! Counting a loop as degree 1 instead of degree 2. A loop adds 2 to the degree of its vertex.
  • ! Confusing the order of vertex pairs in directed graphs; writing \((A, B)\) when the arrow actually points from \(B\) to \(A\), which should be \((B, A)\).
  • ! Forgetting that every tree must be fully connected; drawing a disconnected graph with \(n - 1\) edges and mistakenly calling it a tree.
  • ! Forming closed cycles when asked to draw a tree from a graph.

Misconceptions

Misconception

Any graph with \(n(E) = n(V) - 1\) is automatically a tree.

Correct Fact

The condition \(n(E) = n(V) - 1\) is necessary but not sufficient on its own; all vertices must also be connected with no cycles or loops.

Misconception

In an undirected graph, \((u, v)\) and \((v, u)\) represent two separate edges.

Correct Fact

In an undirected graph, \((u, v)\) and \((v, u)\) represent the exact same edge. They only represent different edges in a directed graph.

Summary

  • Graph: \(G = (V, E)\) where \(V\) is the set of vertices and \(E\) is the set of edges.
  • Degree Sum Formula: \(\sum d(v) = 2 \times n(E)\), which must always be an even number.
  • Loop adds 2 to the vertex degree; multiple edges connect the same pair of vertices.
  • Directed graph: Edges have arrows; \(d(v) = d_{in}(v) + d_{out}(v)\).
  • Weighted graph: Edges carry values representing quantities like distance, cost, or time.
  • Subgraph: A subset of vertices and edges preserving original graph connections.
  • Tree: A connected simple subgraph without cycles, having \(n\) vertices and \(n - 1\) edges.

Short Activity

Complete all parts first, then press the check answer button.

A. Objective Quiz

1 Which of the following sets of vertex degrees cannot form a graph?

2 Which statement is a necessary property of a tree with \(n\) vertices?

B. Fill in the Blanks

3 If a graph has 7 edges, the sum of degrees of all its vertices is .

4 In a directed graph, the degree of a vertex \(v\) is determined by adding the number of edges entering the vertex, \(d_{in}(v)\), and the number of edges leaving the vertex, .

C. Drag and Drop: Match Each Concept to Its Description

Drag each concept to the correct description. On a phone, tap the answer choice first, then tap the description box.

Concept
Simple graph
Loop
Weighted graph
Tree
Description
A graph that has no loops and no multiple edges.CorrectTry againEmpty
An edge that starts and ends at the same vertex, adding 2 to the degree.CorrectTry againEmpty
A graph where each edge is associated with a numerical value such as distance or cost.CorrectTry againEmpty
A connected simple subgraph with \(n\) vertices and exactly \(n - 1\) edges.CorrectTry againEmpty
 

Key Terms

Vertex (bucu) Edge (tepi) Degree (darjah) Simple graph (graf mudah) Loop (gelung) Multiple edges (berbilang tepi) Directed graph (graf terarah) Undirected graph (graf tak terarah) Weighted graph (graf berpemberat) Unweighted graph (graf tak berpemberat) Subgraph (subgraf) Cycle (kitaran) Tree (pokok)
The views expressed in the notes here are those of the contributor and don’t necessarily represent the views of Pandai.
Chapter : Networking in Graph Theory
Topic : Networking
Form 4 Mathematics
Related notes

Report this note
© 2026 Pandai.org All Rights Reserved

Quiz
View video m
Notes
Account