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 :)
girthof 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
dhas at least
- Show that a finite simple graph has at least two vertices with the same degree.
- 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
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
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.