Let $\kappa\geq \aleph\_0$ be a cardinal. Is there a simple undirected graph $G=(V,E)$ such that every simple undirected graph on $\kappa$ vertices is isomorphic to a minor of $G$?



"Universal" infinite graph (with respect to minors)
Yes. In fact, a stronger statement is true: for every cardinal $\kappa$, there is a simple undirected graph $G = (V,E)$ such that every simple undirected graph on $\kappa$ vertices is isomorphic to an induced subgraph of $G$.


There are several ways to see this. My favorite is as follows. First, assume that $\kappa$ is a regular cardinal (otherwise just use $\kappa^+$ instead). Let $V = V\_\kappa$ denote the set of all sets that have rank smaller than $\kappa$, and define $E$ so that $x$ and $y$ are connected if and only if either $x \in y$ or $y \in x$. (In other words, $E$ is the symmetrization of the membership relation.) I claim that this graph has the desired property.


To see this, simply note that if $X$ and $Y$ are disjoint subsets of $V$, and both $X$ and $Y$ have size less than $\kappa$, then (by regularity) there is some $\alpha < \kappa$ such that every "vertex" in $X$ and $Y$ is a set of rank at most $\alpha$. Then there is a set of rank $\alpha+1$ that is connected to everything in $X$ and nothing in $Y$ (namely, the set $X$ itself). This shows that $G$ has the "extension property" (as it's often called for the countable random graph), and it's easy to use this property, along with a standard argument by transfinite recursion, to build a copy of any size-($<\kappa$) graph inside of $G$.


*Notes:*


1. If $\kappa = \omega$, then this construction gives you the countable random graph.
2. If you don't like this construction, you can build a graph G with the "extension property" directly by transfinite recursion.
3. You can use $H\_\kappa$ in the place of $V\_\kappa$ and this argument still works. With a touch more work, this shows that, assuming GCH, there is for any $\kappa$ a graph of size $\kappa$ that contains as an induced subgraph every graph of size less than $\kappa$ (i.e., nice analogs of the Rado graph at higher cardinals). This (or versions of it) is sometimes possible to attain even without GCH, as in the paper of Shelah linked to in Tony's answer.


