Connected and not connected
A graph is connected when a route along its edges joins every pair of vertices. The route may pass through other vertices on the way: two vertices need not be joined directly, only reachable from each other.
The graph below has six vertices and six edges. AB, AC and BC make a triangle, and DE, DF and EF make another. A can reach B and C, but no edge leaves the triangle ABC, so no route from A reaches D, E or F. The graph falls into two pieces, and it is not connected. Each piece is called a component.
Two triangles, ABC and DEF, with no edge between them: two components, so the graph is not connected.
One edge joins the pieces
Add the edge BD. Now A reaches D along A-B-D, and C reaches F along C-B-D-F. Every vertex of one triangle reaches every vertex of the other through B and D, so the graph is connected.
To show that a graph is connected, it is enough to show that one vertex reaches all the others, because any two vertices can then be joined through it. From B, the edges reach A, C and D directly, and E and F through D.
The gold edge BD joins the two triangles, and every vertex can now reach every other.
Subgraphs
A subgraph of a graph keeps some of its vertices and some of its edges, and adds nothing new. An edge can be kept only if both of its ends are kept, because an edge is a join between two vertices.
The seven-edge graph has a subgraph with all six vertices and just the four edges AB, AC, BD and DF; the edges BC, DE and EF are left out. Every vertex is still there, even E, which is now joined to nothing.
Leaving out a vertex takes its edges with it. Remove F, and DF and EF go too. What is left is a subgraph with the five vertices A, B, C, D and E and the five edges AB, AC, BC, BD and DE.
The dashed edges BC, DE and EF are left out. The subgraph keeps all six vertices and the four solid edges, and E is left with no edge.
Trees
A tree is a connected graph with no cycle. A cycle is a route that comes back to its start without using any edge or any other vertex twice, such as A-B-C-A.
Keep the edges AB, AC, BD, DE and DF. This subgraph is connected: from B, the edges reach A, C and D directly, and E and F through D. It has no cycle. A cycle passes through each of its vertices, arriving along one edge and leaving along another, so every vertex on it needs at least two edges. C, E and F have only one edge each, so they lie on no cycle; without them, only A-B-D is left, and a line of three vertices has no cycle either.
In a tree there is exactly one path between any two vertices, where a path is a route that visits no vertex twice. From C to F it is C-A-B-D-F. If there were a second path, it would leave the first one somewhere and join it again further on, and the two different stretches between those points would make a cycle.
The tree in gold: connected, with no cycle, and exactly one path between any two vertices, such as C-A-B-D-F from C to F.
One fewer edge than vertices
The tree has 6 vertices and 5 edges. Every tree has one fewer edge than it has vertices: on n vertices, n − 1 edges.
Grow the tree one vertex at a time. Start with A alone: 1 vertex and no edge. Add B with the edge AB, then C with AC, D with BD, E with DE and F with DF. Each new vertex arrives with exactly one edge. With no edge it would not be joined to the rest, and with two edges it would close a cycle, because its two neighbors are already joined to each other through the tree. So every vertex after the first brings one edge: 6 vertices, 5 edges.
The count also works the other way round. Take the longest path in a tree, here C-A-B-D-E. Its last vertex has no edge except the one the path arrived on: another edge would lead either to a new vertex, making a longer path, or back to a vertex on the path, making a cycle. So every tree with at least 2 vertices has a vertex of degree 1, called a leaf; here the leaves are C, E and F. Remove a leaf and its edge, and what is left is a smaller tree with one vertex and one edge fewer. Repeat until one vertex is left, with no edge: the difference of 1 never changes.
The vertices numbered in the order they join the tree: A first, then B, C, D, E and F. Each one after A arrives with one edge, so 6 vertices carry 5 edges.
A tree has no edge to spare
Add one more edge to a tree, and its two ends are already joined by a path in the tree. The new edge and that path together make a cycle. The path from B to C in the tree is B-A-C, so adding BC closes the cycle A-B-C-A, and the result is not a tree.
Take an edge away instead, and the tree falls into two pieces, because that edge was the only path between its two ends. Removing BD leaves A, B and C in one piece and D, E and F in the other.
So a tree is connected with as few edges as possible, and has no cycle with as many edges as possible: one edge fewer disconnects it, and one edge more makes a cycle.
The dashed gold edge BC would close the cycle A-B-C-A, so the tree with BC added is not a tree.
Spanning trees, and counting edges
A connected graph always contains a tree that keeps all of its vertices, called a spanning tree. Remove an edge that lies on a cycle, one at a time, until no cycle is left. The graph stays connected each time, because the rest of the cycle is another way round.
The seven-edge graph has 6 vertices, so a spanning tree keeps 5 of its edges, and 7 − 5 = 2 must go. Its only cycles are the triangles ABC and DEF, so one edge comes out of each. With 3 choices in each triangle there are 3 × 3 = 9 spanning trees, and the tree above is the one that drops BC and EF.
Counting edges alone does not make a tree. The edges AB, AC, BC, DE and DF are 5 edges on 6 vertices, the number a tree would have, but they make the triangle ABC and a separate piece D, E, F: not connected, and with a cycle. A connected graph with n − 1 edges is always a tree, and so is a graph with no cycle and n − 1 edges. The count needs one of the two conditions beside it.
A graph with no cycle that is not connected is called a forest, and each of its components is a tree. With n vertices in c components, each component has one edge fewer than it has vertices, so the forest has n − c edges. The edges AB, AC, DE and DF on the six vertices make a forest of 2 trees, with 6 − 2 = 4 edges.
Five edges on six vertices, the count a tree would have. But the gold triangle ABC is a cycle, and no edge joins it to D, E and F.
The usual mistakes
Calling a graph connected because every vertex has an edge. In the two triangles every vertex has degree 2, and still no route crosses from one triangle to the other.
Keeping an edge in a subgraph after removing one of its ends. An edge needs both of its vertices.
Giving a tree on n vertices n edges. A tree on 6 vertices has 5 edges; a sixth edge would close a cycle.
Answering how many edges must be removed with how many the tree keeps. The seven-edge graph keeps 5 and loses 2.
Calling a graph a tree because it has n − 1 edges, without checking that it is connected or that it has no cycle.
Pipes and folders
In the first application below, the pipes laid between villages make a forest, so the number of separate groups is the number of villages minus the number of pipes. In the second, a directory of folders and files is a tree, so it holds one more item than it has edges.
Worked example: Pipes Already Laid Between Ten Villages, and the Fewest More That Connect Them All
Question A water company is connecting ten villages, A to J, with pipes. So far it has laid six pipes, joining A and B, B and C, D and E, F and G, G and H, and H and I. No set of these pipes forms a loop. (a) Into how many separate groups do the pipes divide the villages, where the villages in a group are connected to one another by pipes? (b) What is the fewest number of extra pipes that will connect all ten villages, and how many pipes will the finished network then have?
1.Model the network as a graph: a vertex for each village and an edge for each pipe. The groups are the connected components. With no loop, each component is a tree, and the whole graph is a forest.
Each village is a vertex and each pipe an edge. With no loop, the graph is a forest. 2.A tree with k vertices has k − 1 edges. Add this over all the components: if c components hold the 10 villages, the number of edges is 10 − c.
A tree with k vertices has k − 1 edges, so a forest on 10 vertices with c components has 10 − c edges. 3.(a) 10 − c = 6, so c = 4 groups. Check by tracing the pipes: the groups are A, B and C; D and E; F, G, H and I; and J on its own.
(a) 10 − c = 6, so c = 4 groups. 4.A new pipe between two different groups joins them into one group, so each pipe reduces the number of groups by at most 1. To go from 4 groups to 1 takes at least 4 − 1 = 3 pipes, and 3 pipes that each join two different groups are enough.
A pipe between two groups joins them into one. Four groups need 3 pipes to become one. 5.(b) The fewest extra pipes is 3, and the finished network has 6 + 3 = 9 pipes. Check: a connected network with no loop on 10 villages is a tree, and a tree with 10 vertices has 10 − 1 = 9 edges.
(b) 3 extra pipes, and 6 + 3 = 9 = 10 − 1 pipes in the finished tree.
Answer: (a) 4 groups; (b) 3 extra pipes, making 9 pipes in all
Common mistakes
- Answering 4 extra pipes for part (b). Four is the number of groups, and joining 4 groups into one takes one pipe fewer than that.
- Counting only the villages that have pipes and forgetting J. A village with no pipe is a group on its own, a component with a single vertex.
More graphs, degree and trees problems, worked step by step →
Worked example: A Project's Directory of Folders and Files, and How Many Items and Files It Holds
Question On a computer, every file or folder in a project, except the project's top folder, sits directly inside exactly one folder. In one project's directory there are 7 folders, the top folder included. Each folder holds exactly 3 items directly inside it, and a file holds nothing. (a) How many items does the directory contain in all, counting every folder and file and the top folder itself? (b) How many of those items are files?
1.Model the directory as a graph: a vertex for each folder or file, and an edge from each folder to each item directly inside it. Every item except the top folder has exactly one folder above it, so the graph is connected with no cycle: a tree, rooted at the top folder.
One directory that fits: each item is a vertex, with an edge from each folder to each item inside it. The graph is a tree. 2.Count the edges from the folders. Each of the 7 folders has 3 items inside it, so there are 7 × 3 = 21 edges.
Each of the 7 folders has 3 edges down to its items: 7 × 3 = 21 edges. 3.(a) A tree has one more vertex than it has edges, so the directory holds 21 + 1 = 22 items. The extra 1 is the top folder, the only item that is not inside another folder.
(a) A tree has one more vertex than edges, so there are 21 + 1 = 22 items. 4.(b) The files are the items that are not folders: 22 − 7 = 15 files. They are the leaves of the tree, the vertices of degree 1.
(b) 22 − 7 = 15 items are files, the leaves of the tree. 5.Check with the degrees. The top folder has degree 3, each of the other 6 folders has degree 3 + 1 = 4, and each file has degree 1: 3 + 6 × 4 + 15 = 42, which is 2 × 21.
The degrees add up to 3 + 6 × 4 + 15 = 42, twice the 21 edges.
Answer: (a) 22 items; (b) 15 files
Common mistakes
- Answering 7 × 3 = 21 items. That counts every item that is inside a folder and misses the top folder, which is inside none.
- Answering 21 files by taking every item inside a folder to be a file. Six of those items are folders themselves, so the files number 21 − 6 = 15.
More graphs, degree and trees problems, worked step by step →