I wrote the CFG here in Nearley and tried generating some strings… turns out that sure, it only generates strings encoding a graph iff it has a 3k-clique, but it can also generate a lot of strings! Among others, ones that don’t encode a graph at all (and so far that is in fact all I’ve been able to generate). I’ll edit the post with some careful wording to reflect this.