Blog Post 10

\(1\) \(\underline{\text{Trees-A Branch of Discrete Mathematics}}\) Trees provide poets with inspiration as they sway through the breeze and their leaves, bursting with color, rustle in the wind. It is no wonder, then, that mathematicians coined the term “tree” in describing special classes of structured graphs. One author, Joe Malkevitch, makes it his goal to “convince you (readers) that mathematical trees are no less lovely than their biological counterparts.”

In discrete mathematics, and more specifically graph theory, a tree is a connected graph with no cycles. When the graph is not connected, naturally we call this a forest. In addition, a vertex of degree \(1\) is called a leaf. These kind of mathematical structures were first studied by mathematician Arthur Cayley. In \(1889\) Cayley published a formula stating that for \(n \geq 1\), the number of trees with \(n\) vertices is \(n^{n-2}\).

A few other properties of trees include the following:

  • Given two vertices, \(x\) and \(y\), there is a unique path from \(x\) to \(y\)

  • If we remove any edge of a tree, the graph is no longer connected

  • If a tree has \(n\) vertices, then it has \(n-1\) edges

The concept of mathematical trees has applications in various fields including science, the enumeration of saturated hydrocarbons, the study of electrical circuits, and many more (Harary, 1994, p. 4).

One idea that stems from the subject of trees is spanning trees. A spanning tree of a connected, undirected graph is a tree that includes all vertices and some of the edges of the graph such that it becomes a tree. In other words, it contains no cycles. Consider the image below:

Notice that when looking at the figure to the right, all the vertices of the original graph are included but no cycle can be drawn.

From this, given that weights are assigned to each of the edges, one could find what we call the minimum spanning tree. This provides a tree which has the least weight of all the possible trees that could be formed from the original graph. Minimum spanning trees are used, for example, to minimize the cost of power networks, wiring connections, piping, etc.

Referring back to our graph above, we see that this example is also a minimum spanning tree since it consists of all the lowest weighted edges.

\(2\) \(\underline{\text{Suggested Exam Problem}}\)

How many distinct trees can be drawn with \(3\) vertices? Draw them with their correct labels.