Example of a proper class of graphs for which no member is isomorphic to an induced subgraph of a different member?

Perhaps surprisingly, you can't do this without additional set-theoretic axioms (so far as we currently know): the statement that there is no such proper class, Vopenka's principle, is currently not known to be inconsistent with ZFC (in fact, it's generally believed that it is consistent - which is amusing, given that Vopenka didn't think so and introduced it somewhat sarcastically).

Actually, Vopenka's principle says something stronger: that we can always find an elementary embedding. The definition of elementary embedding is a bit technical, but for now it suffices to observe that every elementary embedding is in fact an induced subgraph embedding. (That said, it turns out that we can drop elementarity here and get an equivalent principle - Vopenka's principle is very robust.)


That said, Vopenka's principle is in a precise sense "less likely" than its negation: while we can prove (in a very weak theory - much weaker than ZFC) ZFC + "Vopenka's principle fails" is consistent if ZFC itself is, the theory ZFC + Vopenka proves the consistency of ZFC itself. The standard example of the former is if V=L.

Indeed, Vopenka is extremely strong in terms of consistency strength - it lies fairly high up the large cardinal hierarchy.


Not really.

Vopěnka's principle states that every class of graphs, one embeds elementarily into the other.

But what is an elementary embedding of $G$ into $G'$? Well, it means, in particular, that $G$ is an induced subgraph of $G'$, since having an edge or not having an edge must be preserved by an elementary embedding of graphs.

So what you're asking for is a counterexample to Vopěnka's principle. And if you can prove that there is one, then you give a new upper bound to the large cardinal hierarchy.