DA1, DA6 - The language of graphs
A graph keeps track of which objects are connected, without needing their sizes or positions. DA1 gives the language for connections and routes; DA6 uses that language to recognise simple graphs and trees. You will see why a small change to a drawing can change a graph, while a large change of shape may leave it unchanged.
Vertices, edges and routes
If two roads cross on a map, must you be able to turn from one onto the other? A bridge shows why the answer depends on connections, rather than on the lines' positions.
A graph consists of vertices and edges joining them. A vertex might represent a junction, and an edge a road between junctions. Two vertices are adjacent when an edge joins them; an edge is incident with its endpoints. We draw a labelled dot for each vertex. A crossing without a vertex dot is not a junction. Moving dots or bending lines does not change which endpoints an edge joins.
A loop joins a vertex to itself. Multiple edges are distinct edges joining the same pair of vertices: two roads can join the same junctions. Label them separately when describing a route. Most graphs here are undirected, so an edge can be used either way. A directed edge has an arrow and must be followed in that direction. The undirected rules below must not simply be applied to directed graphs.
[DIAGRAM: asset_name: Vertices edges loops and subdivisions; asset_slug: aqa7367-graph-language; caption: Multiple edges count separately and a loop contributes two to the degree; description: Left is an undirected graph with vertices A B C D, two curved AB edges, BC CD DA and one loop at C. Degrees are A three B three C four D two. Right shows edge PQ subdivided into PX and XQ by a new vertex X.]
The degree of a vertex counts edge ends incident with it. Each ordinary incident edge contributes one; a loop contributes two because both ends are at the same vertex. Thus C in the diagram has degree 4, not 3. A vertex of degree zero is isolated. In a directed graph we distinguish in-degree (arrows entering) and out-degree (arrows leaving); a directed loop contributes one to each.
A route can obey different restrictions. Use these distinctions consistently:
| Route | What may repeat? |
|---|---|
| Walk | Vertices and edges may repeat; consecutive vertices must be joined by the edge used. |
| Trail | No edge repeats, although vertices may repeat. |
| Path | No vertex repeats, so no edge repeats either. |
| Cycle | A closed trail with no repeated vertex except that the final vertex is the starting vertex. In a simple graph it has at least three edges. |
The length of a walk is its number of edges, counted with repetitions, rather than a physical distance. A closed trail can revisit intermediate vertices; it need not be a cycle. For multiple edges a vertex sequence alone may be ambiguous, so name the edges too.
Worked example 1: checking a route
Question. A graph has edges AB, BC, CA, AD and DE. Classify the route B–C–A–D–E and give its length.
Plan. Check consecutive pairs, then look for repeated edges and vertices.
The four consecutive pairs are BC, CA, AD and DE, all present. The five vertices B, C, A, D, E are distinct.
Answer. It is a path of length 4, hence also a trail and a walk; it is not closed.
Check. Five vertices in a path require four connecting edges, agreeing with the direct count.
Keep the graph fixed but insert a detour round its triangle. This changes the route's classification without changing any graph edge.
Worked example 2: a trail that is not a path
Question. In the same graph, classify A–B–C–A–D–E and give its length.
Plan. List used edges and repeated vertices separately.
The edges AB, BC, CA, AD and DE are all distinct. The vertex A occurs twice, but no edge repeats.
Answer. It is a trail and a walk of length 5, but not a path or a cycle.
Check. Its different endpoints A and E rule out a cycle independently of the repeated A.
A subgraph is obtained by selecting some vertices and some of the original edges whose endpoints remain. It need not include every possible original edge between the selected vertices. A subdivision replaces an edge UV by a path U–X–V, or a longer path, using new degree-2 vertices. Merely drawing a bend on UV does not subdivide it: the new vertex must be part of the graph.
Watch out
An edge may be used twice in opposite directions: A–B–A repeats the same undirected edge unless two distinct AB edges are explicitly supplied. A loop contributes two to degree, but using it once counts as one edge of a walk.
Apply both counting rules to a fresh graph.
Simple graphs and connected components
A graph may be straightforward to draw but still fail to be simple, connected, or both: these words describe different properties.
Simple and connected
An undirected simple graph has no loops and no multiple edges. A graph is connected if a path joins every pair of its vertices. A simple-connected graph is a graph that is both simple and connected; the phrase does not mean that it has no cycles.
Connections may be indirect. In the path A–B–C, A and C are not adjacent, but they are connected through B. A connected component is a maximal connected part of a graph: it includes every vertex reachable from any one of its vertices. An isolated vertex is a component by itself. The single-vertex graph with no edges is both simple and connected, since there is no pair that fails the condition.
To find components, start with an unlisted vertex, follow every available edge and collect all reachable vertices. Then repeat from a vertex outside that collection. Moving two components closer in a drawing never joins them; an actual connecting edge is needed.
Worked example 3: identifying components
Question. A graph has vertices A, B, C, D, E, F and edges AB, BC, CA and DE. Is it simple? Find its connected components.
Plan. Check loops and repeated pairs, then group vertices by reachability.
Every edge joins two different vertices and each pair occurs once, so the graph is simple. From A we reach B and C but no other vertex. D and E join each other. F has no edge.
Answer. The graph is simple but disconnected, with components , and .
Check. The three disjoint lists contain all six vertices and every given edge stays within one list.
Now add just enough edges to connect those groups, without introducing a loop or multiple edge.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account