Cardinality of vertex set and edge set of an infinite connected graph Let $G=(V,E)$ be connected such that $|V|$ is infinite. Does it follow that $|E| = |V|$? (It's easy to see that $|E|\leq |V|$.)
 A: First as you note, when $|V|$ is infinite $|E|\leq |V\times V|=|V|$, so we must show the other inequality.
Countable case. If $|V|=\aleph_0$ then consider a finite connected subgraph $V_i$ of cardinality $|V_i|=i$. Since a spanning tree in this subgraph has cardinality $i-1$, the graph has at least $i-1$ edges, for every $i\in\Bbb N$, so $|E|\geq |V|$.
Uncountable case. If $|V|>\aleph_0$ then let $v_0$ be a vertex of maximal degree $\kappa = \max_{v\in V} \mathrm{deg}(v)$. We can count the number of vertices by partitioning them according to their distance from $v_0$:
$$ |V| = \sum_{n\in\Bbb N} |\{ v\in V\mid d(v,v_0)=n\}|, $$
However the next layer can be at most $\kappa$ times larger than the previous layer, because every vertex is connected to a vertex in a previous layer, and every vertex has at most $\kappa$ neighbours:
$$ |\{ v\in V\mid d(v,v_0)=n\}| \leq \kappa |\{ v\in V\mid d(v,v_0)=n-1\}|,$$
so we find the upper bound
$$ |V| \leq \sum_{n\in\Bbb N} \kappa^n = \kappa,  $$
therefore
$$|V| \leq \kappa = \max_{v\in V} \mathrm{deg}(v) \leq |E| \leq |V\times V|=|V|. $$
