Sorry if this is trivial but can someone construct for me any proper class of (not necessarily finite) undirected graphs $C$ for which no graph in $C$ is isomorphic to an induced subgraph of a different graph in $C$?
Or if not then prove that there exists no such class with this property.
It is relatively easy to think of proper classes of graphs, for example the class of complete graphs, since for any set $S$ there exists a unique complete graph $G$ with $V(G)=S$.
However I can't seem to think of any that satisfy the second condition that no graph in the proper class can be isomorphic to an induced subgraph of a different graph in said class.
I have a feeling that it is either impossible to construct such a class or there are many simple examples of such classes which I am just failing to notice due to an error in my intuition, so sorry if it is trivial.
This came up because I was thinking about hereditary graph properties during a bus ride (graph properties closed under induced subgraphs) and I know its not hard to show that for every hereditary property there exists a class of forbiden induced subgraphs which characterise it e.g. trivially take those graphs without the property, though this doesn't seem to imply the existence of a set of forbiden induced subgraphs rather only the existence of a class of such graphs which may or may not be a set as a result if there existed no such class as I described then the existence of a set of forbidden induced subgraphs not just a class of them would in fact be guaranteed for any hereditary graph property.
Best Answer
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.