Lexicographic Product of Extendable Graphs

NEW

Problem: Reconstructed statement: for finite simple undirected graphs, with the standard lexicographic product

where $(u,a)(v,b)$ is an edge iff either $uv\in E(G_2)$, or $u=v$ and $ab\in E(G_1)$, if $G_1$ is $m$-extendable and $G_2$ is $n$-extendable, $m,n\ge0$, then $G_2\circ G_1$ is $(n+1)|V(G_1)|$-factor-critical.

Result: The conjecture is true. In fact, a stronger statement holds:

If $B$ is $(n+1)$-connected and $F$ has a perfect matching, then $B\circ F$ is $(n+1)|V(F)|$-factor-critical.

Let $t=|V(F)|$, so $t$ is even, and put $p=n+1$, $H=B\circ F$. By the generalized Tutte criterion, it is enough to prove that for every $X\subseteq V(H)$ with $|X|\ge pt$,

where $o(\cdot)$ denotes the number of odd components.

For each $v\in V(B)$, let $X_v=X\cap(\{v\}\times V(F))$, $x_v=|X_v|$, and let

Thus clusters indexed by $A$ are completely deleted.

If $|A|\le p-1$, then $B-A$ is connected by $p$-connectivity. Since every remaining cluster is nonempty, $H-X$ is connected. Hence $o(H-X)\le1$. Also

If equality holds, then $|H-X|$ is even, so $o(H-X)=0$; otherwise $|X|-pt\ge1$, so again $o(H-X)\le |X|-pt$.

If $|A|\ge p$, consider components of $B-A$. A component with at least two vertices gives one connected component in $H-X$. Such a component can be odd only if $\sum x_v$ over its base vertices is odd, hence at least $1$. An isolated base vertex $v$ contributes $o(F-X_v)\le x_v$, by Tutte’s theorem applied to the perfect matching of $F$. Therefore

But

so the required inequality follows.

Now apply this with $F=G_1$ and $B=G_2$. Since $G_1$ is $m$-extendable, it has a perfect matching. Since $G_2$ is $n$-extendable, the standard Plummer connectivity theorem gives that $G_2$ is $(n+1)$-connected. Hence $G_2\circ G_1$ is $(n+1)|V(G_1)|$-factor-critical.

Citation: Exact conjecture resolved above. Standard facts used: Tutte’s 1-factor theorem; Plummer’s theorem that every $n$-extendable graph is $(n+1)$-connected.