# Are all almost regular graphs obvious?

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.

-
Not sure, but are $K_{n,n+1}$ obvious? Say $K_{2,3}$? –  joro May 27 '14 at 14:11
If you don't add vertices don't think deleting any edges from $K_{2,3}$ will leave a regular graph on 5 vertices. –  joro May 27 '14 at 14:17
If you add a matching won't you get multiple edges? –  joro May 28 '14 at 10:12

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.

-

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}$.

-
$K_{2,3}$ is obvious because you can add an edge to obtain a $3$-regular graph. However, for $n >2$ this does seem to be a family of counter-examples. Are there others? –  Felix Goldberg May 27 '14 at 14:31
I didn't address adding edges, just deleting edges. Thought you claimed both your constructions work. –  joro May 27 '14 at 14:33
Forgive me if I am being dim, but how do you add an edge to $K_{2,3}$ to get a regular graph? You have three vertices with degree 2... –  Ketil Tveiten May 27 '14 at 14:36
@KetilTveiten Sorry, my mistake. $K_{2,3}$ is also non-obvious. Thanks! –  Felix Goldberg May 27 '14 at 17:19

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.

-
Why The number of vertices of degree 2 is odd? If the number of edges is even this appears false to me. –  joro May 28 '14 at 14:07
@joro: You can choose to add more than one vertex to an edge of the original graph. –  Douglas Zare May 28 '14 at 15:12
That should have been "stringing together $K_d$ graphs." –  Douglas Zare May 28 '14 at 20:28
Can you say a bit more about how you string together the $K_d$ graphs along each edge? The construction I have in my mind creates two degree $d$ vertices for each $K_d$, and so it is no longer true that the degree $d$ vertices are an independent set. Of course, everything is fine for $d=3$. –  Tony Huynh May 29 '14 at 17:00
@Tony Huynh: Add a disjoint $K_d$, then choose an edge $v_1v_2$ of $K_d$ and an edge $w_1w_2$ of the graph $G$. Then you have two opposite edges of the $4$-cycle $v_1v_2w_1w_2$. Replace these with the other two opposite edges $v_1w_1$ and $v_2w_2$. This replacement doesn't change the degrees but it makes the graph connected, and separates those two vertices of $G$. –  Douglas Zare May 29 '14 at 20:12

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

-
Yuster's work is my favourite example of why such irregularity measures are useful :) –  Felix Goldberg May 28 '14 at 13:07

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.

-
How do you prove the first claim? ("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") I don't quite get it. –  Felix Goldberg May 27 '14 at 17:20
@Felix: There are an even number of vertices, so you can pair them up and add an edge for each pair. Their degrees all increase by one, and the other set is unchanged, so you get a regular graph. –  Zack Wolske May 27 '14 at 17:45
But there might be some edges between the even set already in place. In other words - the subgraph induced by the even set is not necessarily empty, how are we sure it has a perfect mathching? I am not saying I think it's wrong, but I don't see how pairing them up can be enough. –  Felix Goldberg May 27 '14 at 18:43
@Felix: Yes, you're right, the edges could already be there. This only works when you don't care if the regular graph is simple. –  Zack Wolske May 27 '14 at 19:43
Ah, good point about the multigraphs. But I really do want my regular graph to be simple in this instance. (Although I mind loops less). –  Felix Goldberg May 27 '14 at 19:55