Esto no es realmente una respuesta, sino una o dos observaciones (espero que pertinentes) que no caben en la sección de comentarios.
Si no insistes en utilizar grafos contables, entonces la respuesta es sí.
Para ver esto, necesitaremos usar un resultado de Robin Thomas. En este documento a Thomas se le ocurre una forma de asociar a cada $X \subseteq 2^\omega$ un gráfico $G_X$ . Si nos fijamos en su construcción, es bastante fácil ver que $G_X$ está siempre conectado (lo utilizaremos más adelante). Demuestra que $G_X$ es un menor de $G_Y$ sólo si $X$ "casi se incrusta" en $Y$ lo que significa que existe una inyección continua desde un subconjunto coontable de $X$ en $Y$ (utilizando la topología estándar del conjunto de Cantor en $2^\omega$ ). En la sección 4 del documento, Thomas dice que Petr Simon ha demostrado que existe un conjunto contable $Y_1, Y_2, \dots$ de subconjuntos de $2^\omega$ tal que $Y_i$ casi no se incrusta en $Y_j$ para cualquier $i \neq j$ . Poniendo esto junto:
Lema: (Simon y Thomas) Existe un conjunto contable de grafos conexos (cada uno de tamaño $\mathfrak{c}$ ) tal que ninguno de estos grafos sea menor que otro.
Esto nos dice automáticamente que existe un conjunto contable de grafos "independientes" en el sentido que describes (aunque los grafos sean de tamaño $\mathfrak{c}$ ). Utilizando el hecho de que todos están conectados, también podemos encontrar un conjunto incontable. Sea $\{G_n : n \in \mathbb N\}$ sea un conjunto de grafos como se describe en el lema. Para cada $A \subseteq \mathbb N$ , dejemos que $H_A$ sea la suma disjunta de todas las $G_n$ avec $n \in A$ . Afirmo que $H_A$ es un menor de $H_B$ sólo si $A \subseteq B$ .
El "si" es obvio: si $A \subseteq B$ puis $H_A$ es un subgrafo de $H_B$ . Para el "sólo si", supongamos $A \not\subseteq B$ y elige $n \in A \setminus B$ . Entonces $G_n$ es un componente conexo de $H_A$ . Supongamos que $\mathcal S$ y $\varphi$ testigo de que $H_A$ es un menor de $H_B$ . Dado que cada miembro de $\mathcal S$ deben estar conectados, y porque $G_n$ está conectado, también debe ser cierto que $\bigcup \varphi[G_n]$ está conectado. Pero esto significa que $\bigcup \varphi[G_n]$ debe ser un subconjunto de algún $G_m$ , $m \in B$ lo que significa que $G_n$ es un menor de $G_m$ . Desde $n \notin B$ , $m \neq n$ y tenemos una contradicción.
Utilizando la afirmación, obtenemos nuestro conjunto incontable de grafos simplemente observando que existe una familia incontable $\{A_\alpha : \alpha \in \mathfrak{c}\}$ de subconjuntos de $\mathbb N$ tal que ningún miembro de esta familia sea subconjunto de otro (basta con una familia casi disjunta). Una familia incontable de grafos independientes es $\{H_{A_\alpha} : \alpha \in \mathfrak{c}\}$ .
Dos observaciones más:
Si puedes encontrar un conjunto independiente contable en $G_{\mathbb N}$ y cada miembro de ese conjunto es un grafo conexo, entonces tu pregunta se responde afirmativamente, ya que el argumento anterior nos permite pasar de un conjunto contable de grafos conexos a un conjunto incontable de grafos.
Como señala Paul McKenney en los comentarios, probablemente sea muy difícil (si es que es posible) encontrar un conjunto independiente infinito en $G_{\mathbb N}$ . Dada la sutileza del documento de Robin Thomas, diría que hacerlo requeriría probablemente mucho esfuerzo. Por otra parte, una respuesta negativa a su pregunta también podría requerir bastante esfuerzo, ya que significaría una extensión del Teorema Robertson-Seymour (y es justo decir que no es un teorema fácil). Así que (aunque me alegra equivocarme), ¡no creo que puedas esperar que esta pregunta se responda fácilmente!
