Dejemos que $\mathcal{G}$ denota el conjunto de todos los grafos infinitos contables (simples no abalorios).
$|\mathcal{G}|\supseteq|\mathbb{R}|$
Para ver esto, construimos una función inyectiva $f:2^\mathbb{N}\rightarrow\mathcal{G}$ (Tomo $\mathbb{N}=\{1,2,\ldots\}$ ), porque $|2^\mathbb{N}|=|\mathbb{R}|$ . Sea $P_n$ denotan el gráfico de trayectorias en $n$ vértices. Obsérvese que $P_1$ es el gráfico trivial sin bordes. Para dos grafos $G_1,G_2$ y denotar su suma por $G_1\oplus G_2$ (gráficamente, nos limitamos a dibujar ambos gráficos uno al lado del otro, sin conectarlos). Esta operación es conmutativa y asociativa y podemos sin problema generalizarla a cualquier conjunto $S$ de gráficos para obtener $\bigoplus_{G\in S}G$ . Además, para dos gráficos $G_1,G_2$ dejar $G_1\vee G_2$ denotan la unión de $G_1$ y $G_2$ . Entonces, para cualquier gráfico $G$ , $G\vee P_1$ es el gráfico que se obtiene añadiendo un nuevo vértice y aristas que conectan el nuevo vértice con todos los vértices de $G$ .
Ahora defina $f$ por $$f(A)=\left(\left(\bigoplus_{n\in A}P_n\right)\vee P_1\right)\oplus \bigoplus_{n\in\mathbb{N}\setminus A} P_n$$
Visualmente, dibujamos cada número en el plano (por su gráfico de trayectoria) y luego pegamos todos los números/grafos que están en el subconjunto $A$ .
$|\mathcal{G}|\subseteq|\mathbb{R}|$
Podemos describir un multigrafo dirigido con una tupla $(V,E,S,T)$ donde $V$ es el conjunto de vértices, $E$ es el conjunto de aristas y $S,T$ son funciones de $E$ a $V$ que describe el vértice origen y el vértice destino de cada arista. El conjunto de todos los multigrafos dirigidos contables puede describirse entonces por $$\mathcal{G}'=\{(\mathbb{N},\mathbb{N},S,T):S,T\in \mathbb{N}^\mathbb{N}\}=\{\mathbb{N}\}\times\{\mathbb{N}\}\times\mathbb{N}^\mathbb{N}\times\mathbb{N}^\mathbb{N}$$
Obsérvese que este conjunto contiene muchos grafos que son isomorfos entre sí. También existe un mapa de inclusión natural desde $\mathcal{G}$ en $\mathcal{G}'$ que puede obtenerse asignando los números naturales a los vértices y a las aristas y una dirección a cada arista, de modo que $|\mathcal{G}|\subseteq|\mathcal{G}'|$ . Además, se sabe que $|\mathbb{N}^\mathbb{N}|=|\mathbb{R}|$ Así que $$|\mathcal{G}'|=|\{1\}\times\{1\}\times\mathbb{R}\times\mathbb{R}|=|\mathbb{R}^2|=|\mathbb{R}|$$ .