A Complete Proof of the Strong Conjecture about $F$-Irregular Graphs

Abstract

A graph $G$ is called $F$-irregular if all its vertices have distinct $F$-degrees, defined as the number of subgraphs of $G$ isomorphic to a given graph $F$ and containing the respective vertex. We prove the Strong Conjecture about $F$-irregular graphs (Dovzhenok, Filuta, and Chuhai, 2024), which states that for every connected graph $F$ of order at least three, there exist infinitely many $F$-irregular graphs. Fundamentally generalizing the classical existence conjecture by Chartrand et al. (1987), this work presents an authorized English translation of our original February 2024 manuscript, which was publicly presented in full at two scientific conferences the same year.