On a maximal distance between graphs

NEW

Problem: Reconstructed statement: for finite simple undirected graphs, let $\mathscr F_{p,q}$ be the class of graphs with $p$ vertices and $q$ edges. Let $d(G_1,G_2)=q_1+q_2-2m(G_1,G_2)$, where $m(G_1,G_2)$ is the maximum number of edges in a common subgraph of $G_1$ and $G_2$. The input has the evident typo $G_1\in\mathscr F_{p,q}$; it should be $G_1\in\mathscr F_{p,q_1}$. For $q_1,q_2\ge1$, characterize when

$$d(G_1,G_2)=q_1+q_2-2.$$

Result: Let $P_3$ denote the two-edge path and $2K_2$ two disjoint edges. Then

$$d(G_1,G_2)=q_1+q_2-2$$

if and only if

$$(P_3\nsubseteq G_1\ \text{or}\ P_3\nsubseteq G_2) \quad\text{and}\quad (2K_2\nsubseteq G_1\ \text{or}\ 2K_2\nsubseteq G_2),$$

where subgraph means not necessarily induced.

Equivalently, using maximum degree $\Delta$ and matching number $\nu$,

$$(\Delta(G_1)\le1\ \text{or}\ \Delta(G_2)\le1) \quad\text{and}\quad (\nu(G_1)\le1\ \text{or}\ \nu(G_2)\le1).$$

Thus, if $\min(q_1,q_2)=1$, equality always holds. If $q_1,q_2\ge2$, equality holds exactly when, after possibly interchanging $G_1,G_2$, one graph is a matching and the other has no two disjoint edges; the latter is a star, or $K_3$, together with isolated vertices.

Proof: Since $q_1,q_2\ge1$, both graphs contain $K_2$, so $m(G_1,G_2)\ge1$, giving $d(G_1,G_2)\le q_1+q_2-2$. Equality holds exactly when $m(G_1,G_2)=1$, i.e. when the two graphs have no common two-edge subgraph. Every simple two-edge graph is isomorphic either to $P_3$ or to $2K_2$. Hence a common two-edge subgraph exists exactly when both graphs contain $P_3$, or both contain $2K_2$. This proves the stated criterion. The reformulation follows because $P_3\subseteq G$ iff $\Delta(G)\ge2$, and $2K_2\subseteq G$ iff $\nu(G)\ge2$.

Verification audit: the reconstructed definition is exactly Šabo’s MCS distance for graphs with the same number $p$ of vertices; no extra hypotheses beyond finite simple graphs and $q_i\ge1$ were introduced; the conclusion is precisely the equality case in Problem 2.

Citation: Definitions and problem: Michal Šabo, “On a maximal distance between graphs,” Czechoslovak Mathematical Journal 41.2 (1991), 265–268. The characterization above is proved here.