Are all almost regular graphs obvious?

Question

Let the maximum and minimum degress of a graph be denoted (as usual) by $\Delta$ and $\delta$ respectively.

A graph is almost regular if $\Delta-\delta=1$.

Now, here is a simple way to generate such graphs: start with a regular graph and delete a matching. Either that or add a matching.

An almost regular graph which is produced from a regular graph by the addition or removal of a matching is obvious.

Can you find examples of non-obvious almost regular graphs? So far, I am unable to produce any but I have a feeling there ought to be some.

A follow-up question, in case non-obvious ones do exist, would of course be to estimate which case is more prevalent.

Answer 1

Here is an expansion of joro's answer.

Claim. $K_{n, n+1}$ is obvious if and only if $n+1$ is even.

Proof. If $n+1$ is even, we can add a perfect matching on the vertices on the right to obtain a $(n+1)$-regular graph. Conversely, if $n+1$ is odd, I claim that $K_{n,n+1}$ is not obvious. Obviously (bad pun), we cannot delete a matching to create a regular graph, since deleting any edge decreases the degree of both a vertex on the left and a vertex on the right. Thus, we must add a matching $M$, and no edge of $M$ can be incident to a vertex on the left, since they already have degree equal to $n+1$. It follows that $M$ must be a perfect matching of the vertices on the right, but this is impossible since $n+1$ is odd.

Answer 2

Don't think just deleting edges from almost regular graph will result in a regular graph of the same order.

Take $K_{2,3}$. By exhaustive search deleting edges couldn't find a regular graph on $5$ vertices.

Same for $K_{3,4}$, so this might apply to $K_{n,n+1}$.

Answer 3

Here is a different generalization of $K_{2,3}$: Take any $3$-regular graph. Subdivide the edges into paths by adding an odd number of vertices. No vertices of degree $3$ in the resulting almost regular graph are adjacent to any other, so there is no way to remove a partial matching to produce a $2$-regular graph. The number of vertices of degree $2$ is odd so there is no matching on the set of vertices of degree $2$.

The same sort of construction can be used to make an almost regular graph $H$ from any regular graph $G$ of odd degree $d \gt 1$ so that $G$ is a minor of $H$ by stringing together $K_{d-1}$ graphs along each edge with an odd number of added vertices.

Answer 4

Here are a few more observations.

(1) Recall a consequence of Dirac's Theorem: A simple graph $G$ on $2n$ vertices admits a one-factor if $\delta(G) \ge n$. (This is a sufficient, but not necessary, condition.)

So, should Zach Wolske's set $D$ induce a subgraph which is at least "half dense", then $D$ contains a perfect matching and his argument works for simple graphs too. A similar thing holds for the set of even vertices $N$ by considering the complement of the induced subgraph. In general, it's polynomial to check for the existence of a perfect matching.

Pushing this a little further, I suspect that obvious graphs are the majority of almost-regular ones (but I have not worked out the details).

(2) As you know, there are various regular graphs which admit no perfect matching. (By the above comments, these graphs need to be fairly sparse.) As examples, there are odd cycles and also that famous cubic graph on 16 vertices (see http://mathworld.wolfram.com/PetersensTheorem.html).

If $G$ is any of these "bad" (say $r$-regular) graphs with $r$ odd, then the disjoint union of $G$ with $K_{r}$ provides a non-obvious almost regular graph. You can't add a matching to the clique, and you can't take one out of $G$. This sort of generalizes the complete bipartite $K_{n,n+1}$ counterexample (upon considering the complement).

(3) I am almost certain you know about Yuster's work on one-factors in almost regular graphs, but those who don't may find this helpful: http://research.haifa.ac.il/~raphy/papers/match-regular.pdf

Answer 5

Partition your graph into vertices of even degree, $N$, and vertices of odd degree, $D$. If the size of both sets is even, then you can add a matching to the set with lower degree to get a regular graph. If there is an odd number of vertices in one set, then it must be $N$ (and thus they can't both have odd cardinality). In this case, if the degrees are $2k-1$ and $2k$, so that the odd degree is smaller than the even degree, then you can add a matching to $D$, since it has an even number of vertices. If the odd degree is greater, you cannot add a matching to $N$, since it has odd cardinality, so you will have to remove a matching from the induced subgraph generated by $D$. It's easy to check if this exists, and that classifies your obvious graphs.

${\bf **Edit**}$ This construction fails to make simple graphs, as Felix points outs. It also can't identify which obvious graphs make simple regular graphs: e.g. {the graph made from $K_4$ minus an edge, $K_6$ minus a matching, and $6$ edges between them, one from each vertex in $K_6$ to give the other vertices degree $4$} is an obvious almost regular graph, but adding a matching to the $K_4$ part won't make a simple graph - you need to remove a matching from the $K_6$ part.