Pancake Graphs: Berge-Tutte obstructions and recursive cost

This note is a visual companion to the pancake graph preprint. The paper computes the conditional fractional strong matching preclusion number of the pancake graphs: the smallest number of deleted vertices and edges that leaves $P_n$ with no fractional perfect matching but also no isolated vertex. The answer, for $n\ge 5$ , is

$\operatorname{cfsmp}(P_n)=2n-4,$

together with a complete list of the fault sets achieving it.

This note is not a replacement for the proof. Its goal is to show the mechanism: any fault set that succeeds must create a Berge-Tutte obstruction, every obstruction comes with a local bill, and the recursive structure of $P_n$ makes almost every bill exceed $2n-4$ .

For background on the recursive decomposition, see Pancake Graphs and their recursive structure.

The obstruction

A graph has a fractional perfect matching exactly when no vertex set $S$ leaves more than $|S|$ isolated vertices after its removal. That is the fractional Berge-Tutte criterion. So if a fault set $F$ destroys every fractional perfect matching of $G$ , some separator $S$ must witness the failure:

$i(G-F-S) > |S|.$

Let $X$ be the isolated vertices of $G-F-S$ . Because the fault set is conditional, $G-F$ has no isolated vertices, so the vertices of $X$ become isolated only once $S$ is removed; in particular $|X|\ge 2$ .

In the picture below, red vertices are the isolated set $X$ , blue vertices are the separator $S$ , gray vertices are the rest of the graph, and the short red stubs mark fault edges that were removed.

A schematic Berge-Tutte obstruction with isolated vertices X after removing S

The key move in the paper is to stop thinking about $F$ directly and instead charge $F$ to its witness $X$ .

The local bill

For a vertex set $X$ , define its isoperimetric cost

$\lambda_G(X)=e(X)+|\partial X|-|X|+1,$

where $e(X)$ counts the edges inside $X$ and $\partial X$ is the set of outside vertices with a neighbor in $X$ . The claim: any conditional fault set with witness $X$ contains at least $\lambda_G(X)$ faults.

The count is direct. Every edge inside $X$ must be a fault, because its endpoints survive yet end up isolated. Every boundary vertex must also be dealt with: either it is deleted, or its edges into $X$ are — unless it belongs to $S$ , in which case the separator handles it for free. The strict inequality $|X|>|S|$ caps the free rides at $|X|-1$ . Adding it up, $F$ contains at least $e(X)+|\partial X|-(|X|-1)$ faults.

The local cost ledger: internal edge faults, paid boundary vertices, and a free separator inside the boundary

For pancake graphs, write $\lambda_n(X)$ for this cost in $P_n$ . The whole matching-preclusion problem now reduces to a single question: show that $\lambda_n(X)\ge 2n-4$ for every candidate witness $X$ .

The recursive ledger

Group the vertices of $P_n$ by last symbol:

$V_i=\{\pi\in S_n:\pi_n=i\}.$

Each $V_i$ is a copy of $P_{n-1}$ , and the full reversal $r_n$ joins the copies by a perfect matching. Write $X_i=X\cap V_i$ for the piece of the witness inside copy $i$ . The bill then decomposes exactly:

$\lambda_n(X)=1+m(X)+b(X)+\sum_i(\lambda_{n-1}(X_i)-1).$

Term	What it counts
$\lambda_{n-1}(X_i)-1$	The internal bill for the piece of $X$ inside copy $V_i$
$m(X)$	Matching edges with both endpoints in $X$
$b(X)$	Mates of $X$ that land outside $X$ and its internal boundary, creating new boundary
$1$	The global $+1$ from the definition of $\lambda$

Every term is nonnegative. This identity is the proof engine: a witness pays a bill inside every copy it touches, plus a toll each time the full-reversal matching fails to line up with $X$ .

Recursive cost ledger for a witness X split across pancake graph copies

The induction, in three ledgers

The main theorem says that, for $n\ge 5$ ,

$\operatorname{cfsmp}(P_n)=2n-4.$

The lower bound is proved by induction on $n$ . Here is the shape of the argument at $n=5,6,7$ . The pictures are schematic: they show only the parts of a witness that matter to the accounting.

$n=5$ : the base case costs six

The recursion bottoms out at $n=5$ , standing on an exhaustive table for $P_4$ : the paper enumerates all $2^{24}$ vertex subsets of the 24-vertex graph $P_4$ and records the minimum of $\lambda_4$ at each size. That is a few seconds of edge counting — no linear programming, no fault-set enumeration.

The $n=5$ case is then a short case analysis. If $X$ sits inside a single copy, every mate leaves the copy, and the identity collapses to $\lambda_5(X)=\lambda_4(X_1)+|X_1|$ , which the table bounds below by $6$ . If $X$ touches three or more copies, the per-copy bills alone give $\lambda_5(X)\ge 1+2\cdot 3=7$ . Witnesses split across exactly two copies are where the girth enters: $P_n$ has no triangles and no 4-cycles, and that rules out every two-copy configuration cheaper than $6$ .

Cost accounting example for a P5 Berge-Tutte witness

$n=6$ : the same shape costs eight

With the $P_5$ bound in hand, the induction step is almost mechanical. A witness inside a single $P_5$ copy carries the old bill of at least $6$ , and its mates under $r_6$ land in other copies as fresh boundary — at least $2$ more. Total: $\lambda_6(X)\ge 6+2=8=2\cdot 6-4$ . The other shapes run the same ledger and also land at or above $8$ .

Cost accounting example for a P6 Berge-Tutte witness

This is the inductive picture: a witness that was barely affordable one level down becomes exactly expensive enough one level up.

$n=7$ : only close pairs stay tight

By $n=7$ the accounting is rigid. A close pair — two vertices that are adjacent or share a common neighbor — hits the target $2n-4=10$ exactly. Anything more spread out pays a separate bill in each occupied copy plus matching tolls, and overshoots.

Cost accounting example showing tight and overpaying P7 witnesses

The pattern in general: the recursive identity keeps adding nonnegative tolls, and the only witnesses that never overpay are pairs of vertices at distance at most two.

The tight obstruction

The equality case has one concrete shape. Take an induced path $u$ – $w$ – $v$ . The witness is $X=\{u,v\}$ , the separator is $S=\{w\}$ , and the boundary to pay is

$B=(N(u)\cup N(v))\setminus\{w\}.$

Because $P_n$ has no triangles and no 4-cycles, $u$ and $v$ are nonadjacent, $w$ is their only common neighbor, and every $y\in B$ has exactly one edge back to $\{u,v\}$ . So $|B|=2(n-2)=2n-4$ , and the optimal fault sets pay each boundary vertex exactly once: delete either $y$ itself or its one edge toward $\{u,v\}$ . Mixing vertex and edge payments freely gives the complete list of optimal sets.

The tight obstruction built from an induced path u-w-v and boundary payments

That is the whole classification: the witness is as small as possible, the separator is the forced common neighbor, and the boundary is paid with no slack.

The proof in one line

Every conditional fault set $F$ has a witness $X$ , and

$|F|\ge\lambda_n(X)\ge 2n-4.$

The first inequality is the local bill; the second is the recursive ledger. Equality forces $X$ to be a close pair with each boundary vertex paid exactly once — precisely the fault sets above.