# 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: