Graph insights

I'll talk about a couple of graph properties that appear in A Course in Combinatorics as problems in the first chapter. Solving each of them was a rewarding experience for me. Knowing the answer will not make you feel good, but solving them might; unless they are too easy or too hard for you. So if you want to have a good week read the problems and then start working :)

1. The girth of a graph is the smallest length of its polygons (cycles). Show that for all d=1.. a graph with girth 5 and whose vertices have degree at least d has at least d2+1 vertices.
2. Show that a finite simple graph has at least two vertices with the same degree.
3. A graph has the property that for all pairs of vertices there is exactly one vertex joined to both vertices of the pair. Show that non-adjacent vertices have the same degree.

Now stop reading.

The first problem made me wonder what is so special about number 5. Now I know but, curiously, wondering about it didn't help solve the problem. What helped was looking at the neighbors of a vertex. Consider all nodes that can be reached in at most two steps from a certain vertex. Clearly, different paths lead to distinct nodes for otherwise we would have found a polygon of size less than 5. The number of paths of length 1 is at least d and the number of paths of length 2 is at least d(d-1). Therefore there are at least 1+d+d(d-1) vertices. In fact we can easily generalize this by considering odd girths 2k+1.

The second problem. I liked this one because of the simple way it is stated. Now I love it because of the simple way it can be solved. As usual I had quite a few false starts while trying to solve it. They were all too complicated. I should learn from this. If the solution I'm constructing starts to look too complicated then I'm on the wrong path. But let's get back to the problem. A simple graph is one with no loops and no parallel edges. The degree of a vertex is one of 0, 1, ..., N-1, where N is the number of vertices. These are exactly N possibilities and if we want to build a graph for which all degrees are distinct we must use all these values. On the other hand it is quite impossible to have in the same graph a vertex with degree 0 and one with degree N-1.

Now the last problem. This one I solved while having tea with my girlfriend. In fact I have used paper sparingly for the other problems as well. Sometimes even paper drives you away from the solution by allowing you and therefore encouraging you to try complicated approaches. A computer is simply evil for tackling such problems. We can learn from this. Even for truly complicated problems for which a computer can genuinely help we must be very careful not to use the computer to complicate more an already complicated problem. Again, back to the problem. For tackling this one we need some terminology and an intermediate step. The terminology will significantly shorten subsequent statements and therefore will make them easier to understand. I will say that vertex C is the common vertex of vertices A and B if and only if it is the only vertex joined to both A and B. The hypothesis can now be restated: "Each pair of distinct vertices has a common vertex".

We need to better understand what the hypothesis tell us about the neighborhood of a vertex V. Look at pairs formed by V with one of its neighbors: the common vertex will also be one of V's neighbors. Therefore V's neighbors come in (joined) couples. Here is the first fact we have found about the graph: all degrees are even.

Now we can attack the conclusion. Consider a pair of non-adjacent vertices (A, B). We will refer to the common vertex of this pair by the letter C. The A's neighbor that is coupled with C is baptized CA, and similarly we baptize vertex CB. The name NA denotes a neighbor of A that is different from C and CA and similarly NB denotes a neighbor of B different from C and CB. Now consider (NA, B) pairs. Their common vertex must be an NB vertex (why are C and CB not possible?). Therefore each NA is joined with exactly one NB. Because of symmetry each NB is also joined with exactly one NA. We are done: the number of NA vertices must equal the number of NB vertices.