Classes of graphs closed under isomorphism Lets consider:
class of graphs closed on isomorphism.
Can anyone try to explain me this term ?   Particulary, can someone give me examples such class and try give some intuition how to recognize/ prove that some class has this property.
Is there important if graph is finite or infinite ?
Thanks in advance.
 A: A class $\mathcal{C}$ of graphs (or, more generally, structures) is closed under isomorphism if whenever $G\in\mathcal{C}$ and $H\cong G$, $H\in\mathcal{C}$ as well.
Basically, this means that whether a graph is in $\mathcal{C}$ or not depends only on what the graph looks like; two graphs that look the same, but are labelled differently (that is, have different underlying sets), aren't distinguished. For example, if the graph consisting of two points $a$ and $b$ connected by an edge is in $\mathcal{C}$, then so is the graph consisting of two points $q$ and $z$ connected by an edge.
The following are examples of classes of graphs which are closed under isomorphism:


*

*The class of planar graphs.

*The class of graphs with no more than $17$ vertices.

*The class of graphs which are trees.

*The class of connected graphs.

*The class of graphs which satisfy $\varphi$, for some first-order sentence $\varphi$.
And so on.
The following classes are not closed under isomorphism:


*

*The class of subgraphs of $G$, for some fixed graph $G$. (Note that the class of subgraphs of any graph isomorphic to $G$, however, is closed under isomorphism.)

*The class of graphs with underlying set $\subseteq\mathbb{N}$.

If you've seen some computability theory before, there's an analogous concept: index sets. Two partial computable functions $\varphi_c$ and $\varphi_d$ are equivalent - written "$\varphi_c\cong\varphi_d$" - if they have the same domain, and their values agree on that domain. (That is, they represent two different algorithms, but those algorithms "do the same thing".) Then an index set is the analogous notion of a class closed under isomorphism: $E\subseteq\mathbb{N}$ is an index set iff $$c\in E, d\cong c\implies d\in E.$$ Note that this is identical language to the above.
