For any set $X$, let $[X]^2 = \big\{\{a,b\}: a, b\in X \land a\neq b\big\}$. Let $\kappa$ be an infinite cardinal. Is there a set ${\cal E} \subseteq {\cal P}([\kappa]^2)$ such that
?
Under the axiom of choice, the answer is yes. Interpret $\kappa$ as its initial ordinal. We take the vertex to consist of distinct vertices $A_\alpha,B_\alpha,C_\alpha,D_\alpha$ for each $\alpha<\kappa$. In each of the graphs, $B_\alpha$ is connected to $A_\alpha$ and $C_\alpha$ and possibly to $D_\alpha$, so that $B_\alpha$ always hes degree $2$ or $3$. $D_\alpha$ will only be connected to $B_\alpha$ if anything, so will have degree $0$ or $1$. We connect $A_\alpha$ to $C_\beta$ for $\alpha<\beta$. For any $S\subseteq\kappa$ let $G_S$ be the graph in which an edge between $B_\alpha$ and $D_\alpha$ is present iff $\alpha\in S$.
If I'm not mistaken, then we can show by transfinite induction of $\alpha$ that in any isomorphism between $G_S,G_{S'}$, $A_\alpha$ goes to $A_\alpha$, $B_\alpha$ to $B_\alpha$ and $C_\alpha$. But since $B_\alpha$ has degree $3$ in $G_S$ iff $\alpha\in S$, it follows that this can truly be an isomorphism only if $S=S'$.
Let's call a graph asymmetric if it has no nontrivial automorphism. It is stated as Lemma 5 on p. 165 of F. Galvin, G. Hesse, and K. Steffens, On the number of automorphisms of structures, Discrete Math. 24 (1978), 161–166 that for each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$. Concerning the proof the authors say only that it "can be proved by induction on $\kappa$". I guess their construction is something like the following.
Lemma. There are infinitely many nonisomorphic asymmetric finite trees.
Proof. For each integer $n\ge7$, the star $K_{1,3}$ has an asymmetric subdivision with $n$ vertices.
Theorem. For each infinite cardinal $\kappa$ there are $2^\kappa$ nonisomorphic asymmetric trees of cardinality $\kappa$.
Proof. We use induction on $\kappa$. Let $\kappa$ be an infinite cardinal. It follows from the lemma if $\kappa=\aleph_0$, or from the inductive hypothesis if $\kappa\gt\aleph_0$, that there are (at least) $\kappa$ nonisomorphic asymmetric trees of cardinality less than $\kappa$. Choose a set $\mathcal T$ of $\kappa$ nonisomorphic asymmetric trees, each of cardinality less than $\kappa$. Given any set $\mathcal S\subseteq\mathcal T$ with $|\mathcal S|=\kappa$ we construct an asymmetric tree $T_\mathcal S$ of cardinality $\kappa$ by taking a new vertex $v$ and edges joining $v$ to one vertex of each tree in $\mathcal S$. To recover $\mathcal S$ from $T_\mathcal S$ we simply delete the unique vertex of degree $\kappa$, and get a forest whose connected components are the elements of $\mathcal S$.
The general fact is that every mathematical structure of size $\kappa$, in a language of size at most $\kappa$, can be coded as a (connected, undirected, simple) graph of size $\kappa$. What I mean is that this coding process respects isomorphism, so that structure $M$ is isomorphic to $M'$ if and only if the corresponding graph encodings are isomorphic as graphs. It follows that since there are $2^\kappa$ many non-isomorphic structures (e.g. partial orders, groups, subsets of $\langle\kappa,<\rangle$, or what have you), there must also be $2^\kappa$ many non-isomorphic graphs.
In this way, the isomorphism problem of $\mathcal{L}$-structures of size $\kappa$ reduces to the graph isomorphism problem, and this is a sense in which graph-isomorphism is complete. For example, since for countable structures such as countable groups or partial orders, the graph-encoding process is Borel, it follows that the isomorphism relation for countable groups or basically for any kind of countable structures is Borel reducible to the graph isomorphism relation on countable graphs, in the sense of Borel equivalence relation theory.
There are many accounts of the graph encoding, and it is a good exercise to construct your own. But to say a little more about it, suppose we have a structure $\langle\kappa,\ldots\rangle$ with domain $\kappa$. We first aim to reduce to directed graphs. We may think of the relations and functions of the structures in terms of their graphs, and thereby reduce to coding subsets of various $\kappa^n$. And we can encode the copies of these $\kappa^n$ and their projection functions, so that we can tell whether a node in the graph is representing an element of $\kappa$ or a pair or a triple and how they project and so on, and then we can also code any subset of these by adding a node that points directly at the satisfying instances, plus some extra rigid structure that uniquely determines the pointing node. Finally, we reduce from directed graphs to graphs. One way to do this is to replace each directed edge with an assemblage of undirected edges, in such a way that we can tell which are the endpoints and which way the original edge pointed.
When I teach my graduate logic course, we usually do this coding explicitly, and the particular encoding that I use results in connected simple graphs.
