Constructing an Infinite Family of Graphs

Question

In a number of graph theory books that I am working through I come across questions that ask something like $\textit{'Construct an infinite}$ $\textit{family of graphs with _________'}$ and state some property in the blank space that the family of graphs have to satisfy. These questions totally stump me, so my question is what, if any, is a good method of attack for these types of questions? Also what is a 'solution' to these questions meant to look like?

As an example, I am currently trying to work through the following problem from John Meier's book $\textit{Groups, Graphs and Trees; An Introduction to the Geometry of Infinite Groups}$ that asks:

Construct infinitely many distinct (2,3)-biregular graphs

In this case I understand what a biregular graph is and can construct a number of distinct graphs by hand, however, I don't understand how to generalise it to get infinitely many distinct graphs of this type.

Answer 1

If you want to construct infinitely many graphs, you want to construct arbitrarily large graphs with the given property. A straightforward approach to try would be to try to find an $n$-vertex graph for any $n$.

This might not always work, because not all values of $n$ are valid. An infinite family also lets you skip values of $n$ that don't work, as long as you still have $n$-vertex graphs for infinitely many $n$. For example:

• If you were looking for examples of $10$-regular graphs, you would not be able to find any for fewer than $11$ vertices. It's okay to skip $n=1, 2,\dots, 10$.
• If you were looking for examples of $3$-regular graphs, you would not be able to find any for an odd number of vertices. It's okay to only take $n=2, 4, 6, 8, \dots$.
• Even finding a graph of some type with, say, $2^{2^k}$ vertices for each $k$ is still an infinite family, as long as any sufficiently large $k$ works.

In your case, there's a simple restriction: a $(2,3)$-biregular graph has $3k$ vertices on one side, and $2k$ vertices on the other, for some $k$. So you might try to find an example of a $5k$-vertex $(2,3)$-biregular graph for each $k$, and that would give an infinite family.

(Or you might discover another restriction, specify which values of $n$ work more precisely, and try again.)

In some cases, part of the challenge might be describing how you actually get the example. This would look like an algorithm: given $k$, here is how you construct a $5k$-vertex graph with the property we want.

Answer 2

The answer to your problem is quite easy. Just observe that if $K_{2,3}$ is the $(2,3)$-biregular graph with $5$ vertices then the distinct union of $n$ $K_{2,3}$ is a $(2,3)$-biregular graph with $5n$ vertices.

A more general way to attack the problem, where you can see the heuristics is the following:

Let $G=(V,E)$ be a $(2,3)$-biregular graph with parts $B$ and $C$, where $\forall b\in B \ \deg_G b=2$ and $\forall c\in C \ \deg_G c=2$. It is easy to see that $2|B|=3|C|$. Indeed, we can count the number of edges of $G$ in two different ways as follows: the number of edges of $G$ that are incident to some vertex in $B$ is equal to $2|B|$, while the number of edges of $G$ that are incident to some vertex in $C$ is equal to $3|C|$. Hence, since every edge of $G$ is between a vertex in $B$ and a vertex in $C$ we have the equality, i.e. $2|B|=|E|=3|C|$. It is easy to solve this Diophantine equation. We get that $|B|=3n$ and $|C|=2n$ for some positive integer $n$.

Therefore, you have restricted considerably the problem of finding $(2,3)$-biregular graphs to bipartite graphs of parts of sizes $3n$ and $2n$ respectively.

This example is not so interesting as it has an easy solution but in general, the strategy to tackle this kind of problems is to gradually restrict the structure of the graph being considered. In many of these problems a nice way to construct the family of graphs is by induction. This example hides an induction in the construction of the graphs, but it is a trivial one!

Answer 3

The question in your first paragraph is way too broad; it's almost like asking "How do I find a graph that satisfies some given conditions?" The difference is, you're asking "How do I find a graph that satisfies some given conditions, where one of the conditions is 'has more than $n$ vertices'?" The question is unanswerable because what gives the problem its flavor is not the part about having more than $n$ vertices, it's the other conditions. If you ask such a general question, the best you can expect is a very general answer, like "Think hard about it."

Your question about $(2,3)$-biregular graphs is the kind we can deal with here. As stated, it's too easy: just consider the graph $nK_{3,2}$, the union of $n$ vertex-disjoint copies of the complete bipartite graph $K_{3,2}$. To make it a little more interesting, lets ask for large connected $(2,3)$-biregular graphs. There are still lots of solutions. Here's one:

Draw an $n\times n$ chessboard, $n\ge3$. Divide each little square into two triangles by drawing a diagonal. Make the chessboard into a torus by identifying the left side with the right side and the top with the bottom. Now each of the $2n^2$ triangles has $3$ sides, and each of the $3n^2$ edges is a side of $2$ triangles, so the triangle-edge incidence graph is a $(3,2)$-biregular graph of order $5n^2$.