In my last post I talked a little bit about what graph theory is and some of the different terms and names that pop up when you read about it. From the assortment of names and pictures you might have gotten the impression that graph theory can get pretty diverse. Not only is it varied in the kinds of graphs that you see, but also in the different things that people are interested in studying. A case in point comes when you talk about caterpillar graphs. As with the last post, a few definitions are in order to understand what is to be said.
The degree of a vertex in a graph (here I am using graph to refer to the simple graphs introduced in post 1) is simply the number of edges incident to it. This does not come up in simple graphs but to be complete I will say that in the case that a vertex is inside of its own loop you count the loop edge's contribution to the vertex twice (i.e. the degree of a vertex that only has a loop incident to it has a degree of 2).
Now for a couple of graphs:
The first one below is an example of a path graph. It's appearance matches the description quite well. All it's really made of is a sequence of vertices and edges which when followed from left to right account for the entire graph. (Pretty informal definition for the time being but it will do) It has two endpoints of degree one and the remaining internal vertices all have degree two. Apart from the tree that just consists of a single isolated node it is the simplest type of tree that you can have.
A cycle in graph theory is what you would visualize a cycle as being in regular life. You have a series of vertices connected to each other in a circular fashion as seen below. The smallest cycle is the loop, followed by a cycle of length two made up of two vertices connected via parallel edges. The smallest simple cycle is the triangle which is made up of three vertices connected by three edges. Similarly there are four cycles, five cycles,...etc.
1. A tree with at least two nodes must have at least two leaves (vertices in a tree of degree one).
2. A tree consisting of n nodes has exactly n-1 edges.
3. There exists a unique path between any two vertices/nodes of a tree.
(And if you're familiar with computer science you will know that binary trees come up a lot when discussing things like binary search trees, heaps, balanced trees, and the implementation of data structures like sets and maps. )
In addition to the general properties listed above, caterpillar trees have their own interesting properties specific to their structure. One way to think of a caterpillar tree is as the result of a sequence of operations where the operation consists of two parts:
1. Add an isolated vertex to the graph.
2. Connect the isolated vertex to an internal node of the original path.
*And of course if none of these operations are performed on the path we can still say that we have a caterpillar!
What are these properties of caterpillar graphs you say? Well here are a couple of them below. Why are they true? That will be the subject of upcoming posts! To derive the first one I will first have to tell you what Hamiltonian graphs and paths are, and I will also have to explain what the square a graph is as well as its corresponding line graph. (Turns out that you can also just talk about the kth power of a graph in general. You can even talk about the square root of a graph!). Until then, see if you can come up with your own proofs. Draw out your own examples and see if you can notice any patterns. And as always, keep on graphing! :-)
Caterpillar properties:
1. The square of a caterpillar graph with at least two vertices contains a Hamiltonian path.
2. Similarly, they are trees whose line graphs contain a Hamiltonian path.
