On a maximal distance between graphs

NEW

Problem: Let $\mathscr F_{p,q}$ denote the family of finite simple graphs with $p$ vertices and $q$ edges, up to isomorphism. For $G\in\mathscr F_{p,q}$, $H\in\mathscr F_{p,r}$, define

where $m(G,H)$ is the maximum number of edges in a common subgraph of $G$ and $H$. For a subfamily $\mathcal A$, $\operatorname{diam}\mathcal A=\max_{G,H\in\mathcal A}d(G,H)$.

Šabo’s Problem 4 asks whether there is a general relation between

and

and whether equality can occur for nontrivial $q_1\ne q_2$.

Result: There is no universal order relation between $A$ and $B$: all three cases $A<B$, $A=B$, and $A>B$ occur with $q_1\ne q_2$ and both individual diameters positive.

Write

Then

Examples:

Proof sketches of the table:

• For $p=4$, any two $2$-edge graphs share at least one edge, and $P_3$ and $2K_2$ show the maximum common subgraph need not have two edges; hence $\operatorname{diam}\mathscr F_{4,2}=2$. Any two $3$-edge graphs on $4$ vertices contain a $P_3$, while $K_3$ and $K_{1,3}$ are not isomorphic, so $\operatorname{diam}\mathscr F_{4,3}=2$. Also a $2K_2$ and a $K_{1,3}$ have only one common edge, so $C_4(2,3)=2+3-2=3$.

• For $p=5$, similarly $\operatorname{diam}\mathscr F_{5,2}=2$ and $\operatorname{diam}\mathscr F_{5,3}=2$. Complementation preserves distance inside a fixed $\mathscr F_{p,q}$, so $\operatorname{diam}\mathscr F_{5,7}=\operatorname{diam}\mathscr F_{5,3}=2$.

• Every $7$-edge graph on $5$ vertices contains both possible $2$-edge graphs, namely $P_3$ and $2K_2$; hence $m(G,H)=2$ for every $G\in\mathscr F_{5,2}$, $H\in\mathscr F_{5,7}$, and

• Every $7$-edge graph on $5$ vertices contains every $3$-edge graph on $5$ vertices. Indeed the four $3$-edge types are $K_{1,3}$, $P_4$, $K_3$, and $P_3\sqcup K_2$; checking complements, whose complements also have three edges, shows each $7$-edge graph contains all four. Thus $m(G,H)=3$ for all $G\in\mathscr F_{5,3}$, $H\in\mathscr F_{5,7}$, and

Therefore Šabo’s equality question has a nontrivial affirmative answer, e.g.

Audit: The examples use exactly Šabo’s metric and fixed-$p$ graph families; no extra hypotheses are introduced. The triples have $q_1\ne q_2$ and positive individual diameters, so the equality example is nontrivial.

Citation: Definitions and problem: Michal Šabo, “On a maximal distance between graphs,” Czechoslovak Mathematical Journal 41 (1991), no. 2, 265–268. The comparison examples above are proved here.