Problems / combinatorics

combinatorics / Design theory

Existence of $t$-Edge-Balanced Graphs for $t \ge 3$

A graph $G$ on $n$ vertices with $k$ edges is $t$-edge-balanced if every graph on $n$ vertices with $t$ edges is contained in exactly the same number of subgraphs of $K_n$ isomorphic to $G$. Infinite families were known for $t = 2$, but no example was known for any $t \ge 3$. Resolved in both directions: $3$-edge-balanced graphs exist, and no nontrivial $t$-edge-balanced graphs exist for $t \ge 4$.