All courses › Discrete Mathematics › Graphs

Graphs

A graph consists of nodes (vertices) and edges between them. It is used to model networks, roads, piping systems and dependencies. The degree of a node is the number of edges going out from it.

∑vdeg⁡(v)=2∣E∣\sum_v \deg(v) = 2|E|handshake lemma
∣E∣max=(n2)|E|_{max} = \binom{n}{2}most possible edges in a simple graph

Symbols

deg⁡(v)\deg(v)degree of node v
∣E∣|E|number of edges
nnnumber of nodes

Example

5 nodes with degrees 2, 3, 3, 2 and 2:

the sum is 12, so the graph has 12/2=612/2 = 6 edges.

The sum of the degrees is always even, because each edge counts twice.
Practise graphs and modular arithmetic for free →

← Combinations · Modular arithmetic →

Part of Discrete Mathematics: Graphs and modular arithmetic.