Network in Graph Theory

A network (graph) is a set of points, called vertices, joined by lines, called edges. This chapter teaches you to read and draw networks, count degrees, find the sum of weights on the edges, and use them to model real situations like routes and connections.

Expect to draw or complete a network from a table or description, count degrees, and sometimes total the weights along a route. Neat diagrams matter, a cramped sketch causes miscounts.

Paper 2 questions are usually well-structured and generous with method marks if your graph is clear.

Every edge touches two ends, so each edge adds exactly 1 to the degree of each of its two vertices, 2 in total. Add up the degrees of all vertices and you must get twice the number of edges: Σ(degrees) = 2 × (number of edges).

This gives two things at once. It is a fast way to find a missing degree when the edge count is known, and it is a self-check: the total of all degrees is always even, so if your degrees add to an odd number you have miscounted somewhere.

A loop counts 2 towards its own vertex, and where several edges join the same pair of vertices, each one is counted separately.

A subgraph is simply part of a network: keep some of the vertices and some of the edges of the original, adding nothing new. A tree is a special connected network with no cycle, you cannot start at a vertex, travel along edges without repeating one, and return to where you began.

Trees have a tidy rule worth knowing: a tree with n vertices has exactly n − 1 edges. So a tree joining 6 towns uses exactly 5 roads.

If a network with n vertices has n − 1 edges and is all in one piece, it is a tree; add one more edge and you create a cycle.

In a directed network each edge is a one-way arrow, so a vertex has two separate counts: its out-degree (arrows leaving it) and its in-degree (arrows entering it). A route must follow the arrows the right way round, you cannot travel against an arrow.

In a weighted network each edge also carries a number: a distance in km, a cost in RM, or a time in minutes. To find the total for a route, list the edges you actually use in order and add only their weights, the vertices themselves carry no value.

Reading the arrows and adding only the edges on your chosen path avoids most of the marks lost in this topic.

This example uses the sum-of-degrees rule to find a missing degree, then totals the weights along a route, two skills Paper 2 often pairs.