Sea $G=(V,E)$ estar conectadas de forma que $|V|$ es infinito. ¿Se deduce que $|E| = |V|$ ? (Es fácil ver que $|E|\leq |V|$ .)
Respuesta
¿Demasiados anuncios?
En primer lugar, como usted señala, cuando $|V|$ es infinito $|E|\leq |V\times V|=|V|$ por lo que debemos demostrar la otra desigualdad.
Caso contable. Si $|V|=\aleph_0$ consideremos entonces un subgrafo finito conexo $V_i$ de cardinalidad $|V_i|=i$ . Dado que un árbol de expansión en este subgrafo tiene cardinalidad $i-1$ el gráfico tiene al menos $i-1$ bordes, para cada $i\in\Bbb N$ Así que $|E|\geq |V|$ .
Caso incontable. Si $|V|>\aleph_0$ entonces $v_0$ sea un vértice de grado máximo $\kappa = \max_{v\in V} \mathrm{deg}(v)$ . Podemos contar el número de vértices dividiéndolos según su distancia de $v_0$ : $$ |V| = \sum_{n\in\Bbb N} |\{ v\in V\mid d(v,v_0)=n\}|, $$ Sin embargo, la siguiente capa puede ser como máximo $\kappa$ veces mayor que la capa anterior, porque cada vértice está conectado a un vértice de una capa anterior, y cada vértice tiene como máximo $\kappa$ vecinos: $$ |\{ v\in V\mid d(v,v_0)=n\}| \leq \kappa |\{ v\in V\mid d(v,v_0)=n-1\}|,$$ por lo que encontramos el límite superior $$ |V| \leq \sum_{n\in\Bbb N} \kappa^n = \kappa, $$ por lo tanto $$|V| \leq \kappa = \max_{v\in V} \mathrm{deg}(v) \leq |E| \leq |V\times V|=|V|. $$
