Counting graph elements
A graph is made from labelled vertices and edges joining them. Count every edge line once, including loops and separate parallel edges
\[\text{one loop}=1\text{ edge},\quad \text{two edge-ends at a loop vertex}=2\text{ degree units}\]
- Count labelled points Each labelled point is one vertex \(\displaystyle A,B,C,D\;\Rightarrow\;v=4\)
- Count each line once Each joining line contributes one to the edge count \(\displaystyle 5\text{ edge lines}\;\Rightarrow\;e=5\)
- Count a loop once A loop contributes one edge, although both of its ends attach to the same vertex \(\displaystyle \text{one loop}\;\Rightarrow\;1\text{ edge}\)
- Count parallel edges separately Two or more edges between the same pair of vertices are counted one at a time \(\displaystyle AB_1,\;AB_2\;\Rightarrow\;2\text{ edges}\)
Worked example
An undirected graph has 6 vertices, 5 other non-loop edges, 2 loops and one pair of parallel edges. Find the numbers of vertices, edges and loops
\[v=6,\quad e=5+2+2,\quad \text{loops}=2\]
- \(\displaystyle v=6\)The graph has six vertices
- \(\displaystyle e=5+2+2=9\)The five other non-loop edges, two loops and two parallel copies are all separate edge lines
- \(\displaystyle \text{loops}=2\)The two loop lines give a loop count of 2
- \(\displaystyle (v,e,\text{loops})=(6,9,2)\)The three counts are 6 vertices, 9 edges and 2 loops
Common mistakes
Counting loop ends as edges
✕\(\displaystyle 1\text{ loop}=2\text{ edges}\)✓\(\displaystyle 1\text{ loop}=1\text{ edge},\quad 2\text{ edge-ends for degree}\)
A loop has two attached ends but is counted as one edge; the two ends matter when finding degreeCollapsing parallel edges
✕\(\displaystyle 2\text{ parallel edges}=1\text{ edge}\)✓\(\displaystyle 2\text{ parallel edges}=2\text{ edges}\)
Parallel edges share endpoints but are separate edge lines and must be counted separatelySwapping vertices and edges
✕\(\displaystyle v=\text{number of edge lines},\quad e=\text{number of labelled points}\)✓\(\displaystyle v=\text{number of labelled points},\quad e=\text{number of edge lines}\)
Vertices are the labelled points, while edges are the lines joining pointsDifficulty levels
introCount vertices and edges in a simple graph with at most one loop
standardCount vertices, edges and loops when a loop and a parallel pair are present
challengeCount mixed graph features and reason backwards from a description of the edge lines
examChoose the edge count from values made by common loop and parallel-edge errors
Questions about this topic
How is a loop counted?+
A loop is one edge because it is one line, even though both of its edge-ends attach to the same vertex
Why are parallel edges counted separately?+
Parallel edges are different edge lines between the same vertices, so each one contributes to the edge count
What is the difference between a vertex and an edge?+
A vertex is a labelled point in the graph. An edge is a line joining two vertices, or joining a vertex to itself when it is a loop
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks
In this chapter
Count the vertices, edges and loops of a graphDegrees, the degree sum, and even and odd verticesGraph types, subgraphs, connection models and method selectionConnected graphs and bridgesIdentify isomorphic graphsPlanar graphs and drawings in planar formFaces and Euler's formulaRepresent a network in a matrixIdentify the network a connection matrix describesClassify a route: walk, trail, path, circuit or cycleEulerian trails and circuits: existence and identificationHamiltonian paths and cyclesRead a weighted graphThe shortest path by inspectionDijkstra's algorithm for shortest distances and routesTrees and spanning treesMinimum spanning trees by Prim's and Kruskal's algorithmsA full network investigation