Good edge-labelling of graphs

NEW

Problem: For finite simple graphs, a good edge-labelling is a map $\lambda:E(G)\to\mathbb R$ such that no ordered pair of vertices is joined by two distinct $\lambda$-nondecreasing paths. A graph is critical if it is not good, but every proper subgraph is good. Let

The conjecture says: for every $c<4$, only finitely many critical graphs satisfy $Ad(G)\le c$.

Result: The conjecture is false.

For every odd $n\ge 9$, define $G_n$ as follows. Take a cycle $x_0x_1\cdots x_{n-1}x_0$. For each $i\in\mathbb Z_n$, add two new vertices $p_i,q_i$, each adjacent exactly to $x_i$ and $x_{i+3}$. Then

Each $G_n$ is bad: in any labelling of the rim cycle, since $n$ is odd, some three consecutive rim labels are monotone, so one rim path $x_i x_{i+1}x_{i+2}x_{i+3}$ is nondecreasing in one direction. The two length-$2$ paths through $p_i$ and $q_i$ are each nondecreasing in one of the two directions. Among these three paths between $x_i$ and $x_{i+3}$, two are nondecreasing in the same direction, contradicting goodness.

It remains to note criticality. Use the standard criterion: a labelling is good if every cycle has at least two local minima, where a local minimum is a maximal block of equal-labelled consecutive edges whose neighbouring cycle-edges have larger labels.

Delete a rim edge, say $x_0x_1$. Label the remaining rim edges alternately by $2,4$, and label each added path by

Every cycle uses at least one added $2$-path. Each such path contributes one label-$1$ edge. If there are at least two separated label-$1$ blocks, we have two local minima. The only exceptional cases are one added path, or two added paths whose label-$1$ edges meet; then the remaining rim segment is alternating $2,4$ and contains another local minimum. Hence the deletion is good.

Delete instead an added edge, say $x_0p_0$. Use the same labelling and additionally set $\lambda(x_0x_1)=0$. Cycles avoiding $x_0x_1$ are handled above. A cycle using $x_0x_1$ has that edge as one local minimum. Any label-$1$ edge not incident with $x_0$ or $x_1$ gives another. Otherwise the cycle can use only the special added paths incident through $x_1$ or $x_0$; the remaining rim segment has alternating labels $2,4$ and, since $n\ge9$, contains an internal local minimum. Thus this deletion is also good.

By symmetry, every edge deletion is good, so every $G_n$ is critical. The graphs $G_n$ are pairwise non-isomorphic because their orders are distinct. Therefore infinitely many critical graphs have average degree $10/3$, refuting the conjecture already for $c=10/3$.

Citation: No known literature source is being invoked for this counterexample. Definitions and the cycle-minimum criterion are standard in this topic; see Araújo–Cohen–Giroire–Havet, “Good edge-labelling of graphs,” Discrete Applied Mathematics 160 (2012), 2502–2513, and Bode–Farzad–Theis, “Good edge-labelings and graphs with girth at least five,” arXiv:1109.1125.