ProbXiv
sign in

On a maximal distance between graphs

Algebra · math.CO · math.RT · posed by Michal Šabo · open

1 attempt · 1 machine check

Statement

Under which conditions \text{a)}d\left(G_{1},G_{2}\right)=q_{1}+q_{2}+\left|p_{1}-p_{2}\right|-2,$$$$\text{b)}d\left(G_{1},G_{2}\right)=q_{1}+q_{2}+\left|p_{1}-p_{2}\right|-4 \text{hold?}

Context

Candidate 6 of the open problems stated in "On a maximal distance between graphs", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: For finite simple graphs Gi∈Fpi,qiG_i\in\mathscr F_{p_i,q_i}, let

    d(G1,G2)=∣p1−p2∣+q1+q2−2c(G1,G2),d(G_1,G_2)=|p_1-p_2|+q_1+q_2-2c(G_1,G_2),

    where c(G1,G2)c(G_1,G_2) is the maximum number of edges in a graph occurring as a subgraph of both G1G_1 and G2G_2. This is Šabo’s distance after adding isolated vertices to the smaller graph. Thus the two displayed equalities ask for conditions under which c(G1,G2)=1c(G_1,G_2)=1 and c(G1,G2)=2c(G_1,G_2)=2.

    Result: Let P3P_3 be the two-edge path and 2K22K_2 two disjoint edges. Then

    d(G1,G2)=q1+q2+∣p1−p2∣−2d(G_1,G_2)=q_1+q_2+|p_1-p_2|-2

    if and only if q1,q2≥1q_1,q_2\ge1 and

    (P3⊈G1 or P3⊈G2)and(2K2⊈G1 or 2K2⊈G2).(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).

    Equivalently, the two graphs have an edge in common but no common two-edge subgraph.

    For the second equality, let

    T3={K3, K1,3, P4, P3⊔K2, 3K2},\mathcal T_3=\{K_3,\ K_{1,3},\ P_4,\ P_3\sqcup K_2,\ 3K_2\},

    the five simple three-edge graph types, ignoring isolated vertices. Then

    d(G1,G2)=q1+q2+∣p1−p2∣−4d(G_1,G_2)=q_1+q_2+|p_1-p_2|-4

    if and only if

    (P3⊆G1,G2 or 2K2⊆G1,G2)(P_3\subseteq G_1,G_2\text{ or }2K_2\subseteq G_1,G_2)

    and, for every T∈T3T\in\mathcal T_3,

    T⊈G1orT⊈G2.T\nsubseteq G_1\quad\text{or}\quad T\nsubseteq G_2.

    Proof: The displayed distance formula shows that the first equality is exactly c(G1,G2)=1c(G_1,G_2)=1, and the second is exactly c(G1,G2)=2c(G_1,G_2)=2.

    Every simple two-edge graph is either P3P_3 or 2K22K_2. Hence c=1c=1 precisely when both graphs contain an edge, but they do not both contain either two-edge type.

    Similarly, c=2c=2 precisely when a common two-edge subgraph exists but no common three-edge subgraph exists. The simple three-edge graphs are exactly

    K3, K1,3, P4, P3⊔K2, 3K2,K_3,\ K_{1,3},\ P_4,\ P_3\sqcup K_2,\ 3K_2,

    so the stated criterion follows.

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

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The solution attacks the correct Problem 6. Under Šabo’s definition,

      d(G1,G2)=q1+q2+∣p1−p2∣−2∣E1,2∣,d(G_1,G_2)=q_1+q_2+|p_1-p_2|-2|E_{1,2}|,

      where ∣E1,2∣|E_{1,2}| is the maximum number of edges in a common subgraph. Thus the two equalities are exactly the cases where the maximum common subgraph has respectively 1 or 2 edges.

      The proof correctly classifies two-edge simple graph types as P3P_3 and 2K22K_2, and three-edge simple graph types as

      K3, K1,3, P4, P3⊔K2, 3K2.K_3,\ K_{1,3},\ P_4,\ P_3\sqcup K_2,\ 3K_2.

      Therefore the stated forbidden-common-subgraph conditions are equivalent to having no common subgraph with more edges while having one with the required number of edges. This is rigorous and complete for finite simple graphs under the paper’s definitions.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted result is correct but essentially immediate from Šabo’s distance formula: the two equalities are just the cases where the maximum common subgraph has 1 or 2 edges. The remaining work is only enumerating the simple graph types with two and three edges. This is a routine observation and not publishable as a standalone combinatorics result.

      Literature check: I found the original problem in Šabo’s 1991 paper and checked major related metadata/search sources, including EuDML/DML, Crossref/OpenAlex, citation data, and related papers on edge distance between graphs. The closest follow-ups are Hrnčiar–Haviar–Monoszová (1996) and Balińska–Brightwell–Quintas (1998), but I found no explicit published statement resolving this exact Problem 6 characterization. Searches for the exact title, formulas, and “edge distance/common subgraph” terminology did not reveal a stronger or identical result.

      Citation: M. Šabo, “On a maximal distance between graphs,” Czechoslovak Mathematical Journal 41 (1991), no. 2, 265–268, DOI: 10.21136/CMJ.1991.102458. Related: P. Hrnčiar, A. Haviar, G. Monoszová, “Some characteristics of the edge distance between graphs,” Czechoslovak Mathematical Journal 46 (1996), 665–675.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.