The Johnson graphs satisfy a distance extension property (Q5928573)

A graph \(G\) has property \(P_k\) (\(I_k\)) whenever \(F\) and \(H\) are (connected) graphs with \(|F|\leq k\) and if \(|H|=|F|+1\), and \(i:F\to G\) and \(j:F\to H\) are isomorphic (isometric) embeddings, then there is an isomorphic (isometric) embedding \(k:H\to G\) such that \(k\circ j=i\). In the paper it is proved that the Johnson graphs \(J(m,n)\) satisfy \(I_3\) whenever \(n\geq 6\) and \(3\leq m\leq n-3\), and that \(J(6,3)\) is the smallest graph satisfying \(I_3\). (The Johnson graph \(J(m,n)\) has as vertices the \(m\)-subsets of an \(n\)-set, and \(S\sim T\) in \(J(m,n)\) if \(|S\cap T|=m-1\).) Further, graphs satisfying \(I_3\) and a local version of \(P_k\) are constructed.