# Antimatching in revolving door graph

$$RD^d$$ is bipartite graph in which the vertices are $$(d−1)$$-element subsets and $$d$$-element subsets of a $$(2d−1)$$-element ground set. Two vertices are adjacent if one of the corresponding sets is a subset of the other.

My question is why any edge together with its incident edges defines an antimatching of $$2d-1$$ edges? And why $$2d-1$$?

Answer probably is related to the fact that this graph is $$d$$-regular but I have problem to justify it.

Let $$G$$ be a $$d$$-regular bipartite graph. And let $$e_{uv}$$ be an edge of $$G$$.

Let $$S$$ the set of $$e_{uv}$$ and all its adjacent edges. Then the size of $$S$$ is $$2d-1$$ : They are $$d$$ edges connected at the vertex $$u$$, and $$d$$ connected at vertex $$v$$. As we double count $$e_{uv}$$, we reduce the count by one, and $$|S|=2d-1$$.

Recall that an antimatching $$A$$ of $$G$$ is a set of edges such that two edges are at most at distance 2, and that the distance between two edges is defined as the distance between corresponding vertices in $$L(G)$$ (the Line graph of $$G$$).

As all edges from $$S$$ are connected to $$e_{uv}$$, then the maximum distance between edges of $$S$$ is 2.

Therefore $$S$$ is an antimatching of size $$2d-1$$.

I think that's all to proove. (I never studied antimatching before, I might be missing something).

Note An antimatching can also be defined (equivalently) as a subgraph with no induced matching of size greater than 1. This is also clearly the case for $$S$$ :

Suppose there exist an induced matching of size 2 in $$S$$. Then it must contains one edge connected to $$u$$ and one connected to $$v$$. But then in order to be induced we would need to include $$e_{uv}$$, and would not be a matching. Hence a contradiction. Therefore the only induced matching of $$S$$ have size 1.