13 Tree Graphs
If a graph is both connected and has no cycles, then it is a tree graph (Benjamin et al. 2017, 68). Recall from sec-cycles in sec-indirect, that a cycle is a path (as defined in sec-paths) that begins and ends with the same node. Thus, in a tree graph, you can never start with a node and trace a sequence of distinct edges and nodes that take you back to the node you started with!
Figure fig-tree-1 shows a tree graph with ten nodes.
We already defined tree graphs as connected graphs with no cycles. This means that if we were to add a single link connecting any pair of nodes to a tree graph (like the one shown in Figure fig-tree-1), it would create a cycle (of some length), and thus the graph would no longer be a tree!
For instance, Figure fig-tree-2 is just like Figure fig-tree-1, except we added the \(\{BH\}\) edge. Note that after doing this we have created the \(BFJEHB\) cycle (a cycle of length five), and thus Figure fig-tree-2 no longer qualifies as a tree graph. So one property of tree graphs goes like this: A graph is a tree graph if adding a single edge creates a cycle of some length.
13.1 Tree Graph Metrics
Tree graphs have another interesting property. The number of edges of a tree graph \(m\) is always equal to the number of nodes \(n\) minus one. Thus, if a graph is a tree graph or order ten, we know it must contain nine edges (it must be of size nine). For instance, in Figure fig-tree, there are exactly nine edges (count them).
In equation form, if \(G(n, m)\) is a tree graph, then:
\[ m = n - 1 \tag{13.1}\]
Using simple algebra, we can also solve for the order of a tree graph if we know the size:
\[ n = m + 1 \tag{13.2}\]
This equation states that the order of a tree graph equals the number of edges plus 1.
13.1.1 Tree Graph Sum of Degrees
Note that, from Equation eq-sumki in sec-degsum, the sum of the degrees of an undirected graph equals twice the number of edges (\(2m\)). Applying this reasoning, we can see that there should be a special formula for the sum of degrees of an undirected tree graph.
The reason is that if we know that:
\[ \sum_i k_i = 2m \tag{13.3}\]
And we also know that \(m = n - 1\) as per Equation eq-tree1, then substituting for \(m\) in Equation eq-tree3, gives us:
\[ \sum_i k_i = 2(n-1) = 2n - 2 \tag{13.4}\]
Thus, in a tree graph, the sum of degrees will always equal twice the number of nodes minus two!
13.1.2 Tree Graph Density
Remember from sec-graphmetrics, that the density of an undirected graph is given by:
\[ d(G)^u=\frac{2m}{n(n-1)} \tag{13.5}\]
But since in a tree graph, \(m = n- 1\), the Equation eq-dens1 turns into:
\[ d(T)=\frac{2(n-1)}{n(n-1)} = \frac{2}{n} \tag{13.6}\]
So in a tree graph, the density is always equal to two divided by the number of nodes!
So if someone were to ask you, what’s the density of the graph in Figure fig-tree-1, you could immediately answer by knowing that the number of nodes is ten: \(d = 2 \div 10 = 0.2\).
13.1.3 Tree Graph Average Degree
Recall from sec-graphmetrics that the graph average degree is just the sum of degrees divided by the number of nodes. But we already know that in a tree graph, the sum of degrees is equal to \(2n - 2\), so that means that the average degree of a tree graph is always equal to:
\[ \bar{k} = \frac{2n - 2}{n} \tag{13.7}\]
So without even looking at the the graph’s degree sequence and summing each number, I know that the average degree of Figure fig-tree has to be equal to \([(2 \times 10) - 2] \div 10 = (20 - 2) \div 10 = 18 \div 10 = 1.8\). Neat!
13.1.4 Path and Connectivity Tree Graph Properties
Tree graphs have four other unique properties.
- If \(G\) is a tree graph, then every node \(V\) in \(G\) is linked to every other node via a single path.
- The one path connecting each pair of nodes is unique, that is, a sequence of nodes and edges that is distinctive for that node pair and does not repeat for any other pair.
- Removing even a single edge of a tree graph disconnects the graph. Every edge of a tree graph thus counts as a bridge as discussed in sec-indirect.
- Following (3), if we disconnect a tree graph by removing an edge, the resulting connected components are also trees.
We can verify properties (1) and (2) by examining Figure fig-tree-1. There’s only one path connecting nodes \(A\) and \(E\), and that’s \(\{AD, DF, FJ, JE\}\). In the same way, there’s only one path connecting \(A\) and \(C\), and that’s \(\{AD, DF, FJ, JE, EC\}\). Both of those paths are unique.
We can check property (3) by imagining the removal of a single edge from any of the graph shown in Figure fig-tree-1. You can verify that this would indeed disconnect that graph.
For instance, Figure fig-tree-3 is just the same as Figure fig-tree-1, except that we have removed the \(\{DF\}\) edge. As you can see, the graph is indeed now split into two components.
This last thing means that every edge in a tree graph is a bridge as defined in sec-graphconnectivity. Note that when we disconnect a tree graph by removing an edge (as in Figure fig-tree-3) then the resulting two components are also tree graphs!
Another way of saying the last thing is that trees are minimally connected graphs. That is, they are connected graphs that are connected using the smallest possible number of edges that we can use to connect a graph with that number of nodes. We will in a bit that this property allows us to define a new graph metric called the graph efficiency.
A disconnected graph whose components are also trees is called (you guessed it) a forest. Figure fig-tree-3 is a forest with ten nodes. The giant component of the forest in Figure fig-tree-3 contains six nodes \(\{B, C, E, F, H, J\}\) and the smaller component (a line graph as defined below) contains the other four nodes \(\{A, D, G, I\}\)
13.2 Special Types of Tree Graphs
As Figure fig-trees shows, tree graphs come in different configurations, some of which are of particular note.
13.2.1 The Line Graph
Note, for instance, that Figure fig-trees-1 is just a straight path between two nodes. This graph is a tree because it is connected and has no cycles. A graph like Figure fig-trees-1, which is just a single long path with some set of nodes, is also called the line graph. Line graphs are distinguished by their order and can be referred to as \(L_n\), where \(n\) is the number of nodes. Thus, \(L_5\) is the line graph shown in Figure fig-trees-1; a line graph with five nodes.
What are line graphs useful for? Well, they can be used to model the social phenomenon known as the “telephone game.” We can set up people in a line graph in a laboratory, have nodes pass a message, a piece of gossip, or a story along the line, and see how different the original message relayed by \(A\) is by the time it gets to \(E\). Obviously, the longer the number of edges in the line, the more distortion we should expect at the other end.
13.2.2 The Star Graph
Note also the graph that is just a central node connected to all the other end-point nodes, which are not themselves connected to one another; for example, Figure fig-trees-2 also counts as a tree. This graph is sometimes called the star graph. As with line graphs, we can refer to star graphs by a letter and a number indicating their order, such as \(S_n\). Thus, \(S_7\) is the star graph with seven nodes as in Figure fig-trees-2.
Star graphs are useful for modeling centralized systems, such as the airport network we saw in sec-networks. Such hub-spoke systems feature a central node (the hub) connected to a bunch of end-point nodes not connected to one another (the spokes), as when a big airport (like LAX) sends flights to smaller regional airports. In this system, LAX is the “hub” at the center of the star, and the smaller airports are the “spokes” at the end.
13.2.3 Caterpillar Graphs
Tree graphs with an even number of nodes can sometimes be drawn like the ones in Figure fig-trees-3. This is a line graph on top, with edges sticking out of each node, connecting to an equal number of endpoint or pendant nodes (half of the other nodes in the graph).
Because of the shape they form, these tree graphs are sometimes called caterpillar graphs, with the line graph at the top playing the role of the caterpillar’s “body” and the edges incident to the end point pendant nodes playing the role of the “legs.” Figure fig-trees-3 is a caterpillar graph of order eight.
13.3 The Graph Efficiency
Using some of the properties of tree graphs mentioned above, Krackhardt (1994) proposes a measure for how economical the connectivity of a given graph is called the graph efficiency \(F(G)\).
According to Krackhardt, a graph is efficiently connected if its connectivity is accomplished using the minimum possible number of edges. Thus, a tree graph is a maximally efficient graph \(F(G) = 1.0\). The idea is then to compare an observed graph with a tree of the same order and see how closely it resembles it.
Krackhardt proposes the following formula to compute the efficiency of a graph:
\[ F(G) = 1 - \left[\frac{2(m - n + 1)}{(n-1)(n-2)}\right] \tag{13.8}\]
Where \(m\) is the number of edges and \(n\) is the number of nodes. Note that when the graph \(G\) is a tree, the graph \(m = n - 1\). This means that the numerator of Equation eq-eff turns into: \(2(n - 1 -n + 1) = 2 \times 0 = 0\). This means the whole fraction on the right side of Equation eq-eff is zero, and \(1 - 0 = 1.0\), which is maximum efficiency.
As the graph deviates from that by having more edges than a tree, then the fraction on the right side of Equation eq-eff turns into a number that approaches 1.0, which means that the efficiency becomes smaller when we subtract that number from 1.
Let’s consider an example. Of the two graphs shown in Figure fig-eff, which is the one that’s most efficiently connected? Well, the graph in Figure fig-eff-1 has five nodes and seven edges, which means that its efficiency is equal to:
\[ 1 - \left[\frac{2(7 - 5 + 1)}{(5-1)(5-2)}\right] = 1 - \left[\frac{2(2 + 1)}{4 \times 3}\right] = \]
\[ 1 - \left[\frac{2 \times 3}{12}\right] = 1 - \left[\frac{6}{12}\right] = 1 - 0.5 = 0.5 \]
The graph in Figure fig-eff-2, on the other hand, has seven nodes and ten edges, which means that its efficiency is equal to:
\[ 1 - \left[\frac{2(10 - 7 + 1)}{(7-1)(7-2)}\right] = 1 - \left[\frac{2(3 + 1)}{6 \times 5}\right] = \]
\[ 1 - \left[\frac{2 \times 4}{30}\right] = 1 - \left[\frac{8}{30}\right] = 1 - 0.27 = 0.73 \]
So it looks like the graph in Figure fig-eff-2 is more efficiently connected than the one shown in Figure fig-eff-1!
Note also that the complete graph of any order is maximally inefficient according to Equation eq-eff. For instance, we know from sec-graphmetrics that the complete undirected graph of order five has to have \(5(5-1) \div 2\) edges (the graph maximum size), which is equal to \((5 \times 4) \div 2 = 10\).
So when we substitute these numbers into Equation eq-eff, we get:
\[ 1 - \left[\frac{2(10 - 5 + 1)}{(5-1)(5-2)}\right] = 1 - \left[\frac{2(5 + 1)}{4 \times 3}\right] = \]
\[ 1 - \left[\frac{2 \times 6}{12}\right] = 1 - \left[\frac{12}{12}\right] = 1 - 1 = 0 \]
Showing that the complete graph is minimally efficient!
13.4 Spanning Trees
A connected subgraph of a larger graph (see sec-subgraphs) that contains every node of the original graph but that is also a tree graph as defined earlier, is called a spanning tree of the original graph.
Figure fig-span-1 shows a standard undirected graph with order six and size eleven (six nodes eleven edges). Obviously that graph is not a tree, as it contains many, many cycles (e.g., AEDA, FBEDF, BAECB, etc.). However, by deleting the edges that form those cycles we can create a tree graph that keeps everyone connected but pares down the number of edges from the original eleven to the \(n - 1 = 6 - 1 = 5\) we need to create a tree from the original graph.
Such a spanning tree obtained by edge deletion from Figure fig-span-1 is shown in Figure fig-span-2. We can see that Figure fig-span-2 is just an edge-deleted subgraph (see sec-subgraphs) of Figure fig-span-1 obtained by deleting the \(\{AF, DF, AD, AE, AC, BE\}\) edges.
Generally, there will be multiple ways of obtaining a spanning tree from a graph via edge deletion that results in different spanning trees. For instance, Figure fig-span-3 is another spanning tree obtained from Figure fig-span-1, obtained by deleting the \(\{AF, AD,AC, BE, BC, DE\}\) from the original. Figure fig-span-4 shows yet another spanning tree obtained from Figure fig-span-1.
Note that the three graphs in Figure fig-span-2, Figure fig-span-3, and Figure fig-span-4 all count as tree graphs. They all have five edges (as we would expect a tree graph with six nodes to have), all of the edges are bridges (removing one would disconnect the graph), and adding just one more edge would create a cycle.