Graph types, subgraphs, connection models and method selection practice questions | General Mathematics (Year 12, VCE Units 3 & 4)

Graph models and structure

A graph model separates the objects from the direct connections between them. Structural checks can then count vertices and edges, test subgraph membership, or count the pairs in a complete graph

\frac{n(n-1)}{2}

Objects are vertices Use one vertex for each object or location in the model \(\displaystyle \text{objects}\longrightarrow V\)
Direct connections are edges Use an edge to represent each stated direct connection between two vertices \(\displaystyle A\!-!B\in E\)
A subgraph uses parent elements A subgraph may omit vertices or edges, but it cannot add an element that is absent from the parent \(\displaystyle V'\subseteq V,\quad E'\subseteq E\)
Complete graphs use unordered pairs A complete simple graph has one edge for each unordered pair of distinct vertices \(\displaystyle K_6:\;\frac{6(6-1)}{2}=15\)

Worked example

A simple graph has 7 vertices and 18 existing edges. How many additional edges are needed to make it complete?

n=7,\quad e=18

\(\displaystyle \frac{7(7-1)}{2}=\frac{7\times6}{2}=21\)A complete graph has one edge for each unordered pair of vertices
\(\displaystyle 21-18=3\)Subtract the 18 existing edges from the 21 edges required
\(\displaystyle \boxed{3}\)Three additional edges are needed

Common mistakes

Swapping graph roles

✕\(\displaystyle \text{objects}=E,\quad \text{direct connections}=V\)✓\(\displaystyle \text{objects}=V,\quad \text{direct connections}=E\)

Vertices represent the objects, while edges represent the direct connections between them

Counting ordered pairs

✕\(\displaystyle 6(6-1)=30\)✓\(\displaystyle \frac{6(6-1)}{2}=15\)

Each undirected edge joins an unordered pair, so counting both orders doubles the edge count

Keeping every parent edge in a subgraph

✕\(\displaystyle E'=E\)✓\(\displaystyle E'\subseteq E\)

A subgraph may omit parent edges but cannot add edges

Difficulty levels

introClassify a graph from its vertices, edges and structural properties

standardRecognise a subgraph or complete graph from its elements and connections

challengeModel direct connections, count missing complete-graph edges, or select a method from the task

examSelect the graph classification, model, edge count or method that matches the stated structure

Questions about this topic

How many edges does a complete simple graph with n vertices have?+

It has one edge for each unordered pair of distinct vertices, so the number of edges is n(n − 1) divided by 2

What makes one graph a subgraph of another?+

Every vertex and edge in the smaller graph must occur in the parent graph. The smaller graph may omit parent vertices or edges. Every retained edge must join two retained vertices

Why is the complete-graph formula divided by 2?+

The product n(n − 1) counts each pair twice, once in each order. An undirected edge represents the pair only once

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 graph Degrees, the degree sum, and even and odd vertices Graph types, subgraphs, connection models and method selection Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula Represent a network in a matrix Identify the network a connection matrix describes Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection Dijkstra's algorithm for shortest distances and routes Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms A full network investigation