EN
Book a Trial Class

Network in Graph Theory · Form 4

Network in Graph Theory: Worked Examples (Easier)

Reads a network by naming its vertices and edges, counting the degree of each vertex, and using the rule that the degrees add up to twice the number of edges. Best for students meeting graph-theory language for the first time.

Written by the spmmath.com.my editorial team.

Worked example 1

A graph has vertices A, B, C, D and E. The edges are AB, AC, AD, BC and CE.

State the number of vertices and edges, write down the degree of each vertex, and verify that the sum of the degrees equals twice the number of edges.

  1. Count the vertices: A, B, C, D, E, so there are 5 vertices.
  2. Count the edges listed: AB, AC, AD, BC, CE, so there are 5 edges.
  3. Degree of A = edges meeting A = AB, AC, AD → 3.
  4. Degree of B = AB, BC → 2; degree of C = AC, BC, CE → 3.
  5. Degree of D = AD → 1; degree of E = CE → 1.
  6. Sum of degrees = 3 + 2 + 3 + 1 + 1 = 10, and 2 × 5 edges = 10, they match.

Worked example 2

A directed graph has vertices P, Q, R and S with directed edges P→Q, P→R, Q→R, R→S and S→P. Find the out-degree and in-degree of each vertex, and state the total number of directed edges.

  1. Out-degree counts the arrows leaving a vertex; in-degree counts the arrows entering it.
  2. P: leaves to Q and R → out-degree 2; arrow in from S → in-degree 1.
  3. Q: leaves to R → out-degree 1; arrow in from P → in-degree 1.
  4. R: leaves to S → out-degree 1; arrows in from P and Q → in-degree 2.
  5. S: leaves to P → out-degree 1; arrow in from R → in-degree 1.
  6. Total directed edges = sum of out-degrees = 2 + 1 + 1 + 1 = 5.

Worked example 3

A connected network of 9 computers is wired as a tree, with no loop of cable anywhere. How many cables are used?

Explain your reasoning.

  1. A tree is a connected graph that contains no cycle.
  2. For any tree, the number of edges = number of vertices − 1.
  3. Here the vertices are the 9 computers, so v = 9.
  4. Number of cables = v − 1 = 9 − 1 = 8.

Worked example 4

A graph has five vertices with degrees 3, 3, 2, 2 and 2. Find the number of edges in the graph.

  1. The sum of all degrees equals twice the number of edges: Σ degrees = 2E.
  2. Add the degrees: 3 + 3 + 2 + 2 + 2 = 12.
  3. So 2E = 12, giving E = 12 ÷ 2 = 6.

Worked example 5

A graph has 5 vertices, and every vertex is joined to every other vertex exactly once (a complete graph). Find the number of edges.

  1. In a complete graph each vertex joins the other (n − 1) vertices, so each has degree n − 1 = 4.
  2. Number of edges = n(n − 1) ÷ 2.
  3. Substitute n = 5: 5 × 4 ÷ 2 = 20 ÷ 2 = 10.

Worked example 6

In a road network, town P is joined directly to towns Q, R, S and T. Town Q is also joined directly to town R.

Write down the degree of P and the degree of Q.

  1. The degree of a vertex is the number of edges meeting at it.
  2. P is joined to Q, R, S and T, that is 4 edges, so degree of P = 4.
  3. Q is joined to P and to R, that is 2 edges, so degree of Q = 2.

Worked example 7

A network has one central hub H connected directly to four points W, X, Y and Z, with no other connections. State the degree of H and the degree of each of W, X, Y and Z.

  1. H is connected to W, X, Y and Z, so degree of H = 4
  2. Each of W, X, Y, Z is connected only to H, so each has degree 1

Worked example 8

A graph has 7 edges. Find the sum of the degrees of all its vertices.

  1. Sum of degrees = 2 × number of edges
  2. Sum of degrees = 2 × 7
  3. Sum of degrees = 14

Source:DSKP KSSM Mathematics Form 4 and 5 (Versi English)

Book a Trial ClassOne-hour paid trial · Same-day reply · from RM50/hr

Frequently asked questions

What kind of skills do easy network (graph theory) questions test?

At easy level, questions check whether you can read a network diagram correctly, counting vertices, edges, and the degree of a vertex, or completing a simple diagram from a description. There is little calculation; accuracy comes from careful counting and knowing that the degree of a vertex is the number of edges meeting at it.

How do I avoid careless counting mistakes in easy network diagrams?

Mark each vertex with a letter and tick off every edge as you count it, rather than scanning the diagram by eye. For degree, trace each edge touching a vertex one at a time, a loop at a vertex counts twice toward its degree, which is a detail many students miss on their first attempt.

Why is drawing the network diagram neatly important even at easy level?

A cramped or overlapping diagram makes it easy to miscount edges or misplace a vertex, and the examiner also needs to see your diagram clearly to award marks. Space vertices out, use straight lines where possible, and label every vertex, a tidy diagram protects marks that a rushed one can quietly lose.

Book a Trial Class

Book a Trial Class
One-hour paid trial · Same-day replyfrom RM50/hr
Book a Trial Class