3
$\begingroup$

So I am studying for an exam on Discrete Mathematics coming up in a few weeks, when looking past papers it seems that my lecturer enjoys asking questions of the form

"Find all n-regular graphs on m vertices. Justify your answer."

Where he will replace m and n with actual numbers rather than having us deal with the arbitrary case. However, these questions take me ages since I create, for a fixed m and n, all the n-regular graphs on m vertices that I can think of, check that they are not isomorphic and hope i have found all of them. Is there a better way of approaching this question?

For example;

'Find all 5-regular graphs on 8 vertices.'

Any help is appreciated.

$\endgroup$
  • $\begingroup$ General advice is to split the task into disjoint cases, and keep doing this until you can say "okay, then this configuration can be extended either by this edge, or this edge, or this edge" and know that your list is exhaustive. Specific advice depends greatly on how big $m$ and $n$ tend to be; can you give an example or two? $\endgroup$ – Misha Lavrov Oct 22 '17 at 4:31
3
$\begingroup$

Here are some good techniques to try.

Take the complement.

Finding $5$-regular graphs on $8$ vertices may sound intimidating, but the complement of any such graph is a $2$-regular graph on $8$ vertices. (Choosing $5$ neighbors for a vertex is equivalent to choosing $2$ non-neighbors.)

Any $2$-regular graph simply consists of several cycles. This can be a single cycle of length $8$, two cycles of length $4$, or one cycle of length $5$ and one of length $3$. So we've found all the $2$-regular graphs, and therefore all the $5$-regular graphs.

Do casework by girth.

The girth of a graph is the length of the shortest cycle. Does your graph contain a $3$-cycle? If so, you can let $x$, $y$, and $z$ be its three vertices, and think about what else the neighbors of $x$, $y$ and $z$ can look like. If not, you can take four vertices in a $4$-cycle, and consider their vertices (with the further assumption that no $3$-cycles exist, which makes your life much easier).

The six $3$-regular graphs on $8$ vertices can be found by this approach. They fall into the following cases:

  • If the three vertices in a cycle all share a common neighbor, you get the disjoint union of two $K_4$'s.
  • If two of them share a common neighbor, then there is exactly one way to complete the graph.
  • If all three of their remaining neighbors are different, then that's six vertices. There are two ways to complete the graph depending on whether there's an edge between the two remaining vertices or not.
  • Finally, with the strong constraint that there are no $3$-cycles whatsoever, we get two more graphs.

(This table on Wikipedia lists all of them except the single disconnected example.)

Find a Hamiltonian cycle.

Regular graphs, especially with relatively few vertices, are often guaranteed to have a Hamiltonian cycle:

  • A $k$-regular graph on $2k$ vertices or fewer must have one by Dirac's theorem.
  • This paper says that all $k$-regular connected graphs on $2k+2$ vertices or fewer have a Hamiltonian cycle.
  • It cites an earlier (and more interesting) result of Jackson that all $k$-regular $2$-connected graphs on $3k$ vertices or fewer have a Hamiltonian cycle.

(A $2$-connected graph is one that cannot be disconnected by deleting a vertex. You can deal with graphs that are not $2$-connected separately, if this case comes up.)

If a graph contains a Hamiltonian cycle, then we can take advantage of this by having fewer edges to distribute. For example, we can find all the $4$-regular graphs on $8$ vertices this way. Once the Hamiltonian cycle is removed, what is left is either:

  • Another Hamiltonian cycle.
  • Two cycles of $4$ vertices each.
  • One cycle of $3$ vertices and one of $5$ vertices.

This doesn't quite tell us that there are only three such graphs (in fact, there are six; see this list) because the Hamiltonian cycle and the remainder of the graph can fit together in several ways, but it gives us three cases to consider and a lot of information about each case.

And for $3$-regular $8$-vertex connected graphs, if the Hamiltonian cycle is removed, only a perfect matching remains, and it is easy to go through the perfect matchings and see which ones give different graphs.

$\endgroup$
  • $\begingroup$ Very Helpful, thank you so much. $\endgroup$ – Jandré Snyman Oct 22 '17 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.