Minimal Graphs and Trees, Part I
Suppose you're building a network, anything from computers to roads, where the cost of building an edge is a factor. Is there a way to find the smallest possible graph?
What You Should Learn
Let's say you're trying to build a computer network like the ones in the previous section where the vertices are computer networks in separate buildings. High speed computer cable isn't cheap so you want to use as little as possible but, once the network is set up, the connections are so fast that it doesn't matter how many edges a connection has to pass through to get to where it's going. In other words, we would like to construct a system where there is exactly one path between any two points since, if there were multiple paths, we would have used cable we didn't need to.
Specifically, we need a network that has a path connecting every vertex to every other vertex, i.e. it has to be connected, and it also has to have no cycles. Not having cycles will ensure that there's only one path between any two points. Before we can go in search of a solution to what's called the Minimal Connector Problem we need some new language.
Any connected graph with no cycles is called a tree. A graph without any cycles is called a forest.
A tree is what we were discussing in the previous paragraphs. It's a graph that connects every point to every other point in exactly one way. A forest is a collection of trees.
Trees get their name from their appearance. Like the graphs to the right, their branching nature often resembles real world trees. An alternative way to identify a tree is to look for bridges. Individually the two graphs are called trees. Taken together as one big, disconnected graph they're a forest.
Another way to identify a tree is to look for bridges. In a tree every edge is a bridge. If an edge weren't then it could be removed and every vertex could still connect to every other vertex.
Since you know that both of the graphs on the right are trees use them to confirm the following equation.
If G is a tree of order p and size s then s = p - 1.