关于顶点为可数集的无限有向图边集是否至多可数的问询

Great question—let’s break this down clearly, since the answer hinges on one key detail about the graph: whether we allow multiple edges (multiedges) between the same pair of vertices.

Case 1: Simple Directed Graphs (No Multiedges) #

If we’re talking about a simple directed graph (where for any two vertices ( u, v \in V ), there’s at most one edge from ( u ) to ( v )), then yes—the edge set ( A ) is definitely at most countable.

Here’s the reasoning:

• Since ( V ) is countable, we can list all its vertices as ( v_1, v_2, v_3, \dots ).
• Every edge in ( A ) corresponds to an ordered pair ( (v_i, v_j) ) where ( i, j ) are positive integers.
• The set of all such ordered pairs ( V \times V ) is countable (we can enumerate them using a diagonalization argument, just like how we prove the set of rational numbers is countable).
• Since ( A ) is a subset of ( V \times V ), any subset of a countable set is either finite or countable—so ( A ) is at most countable.

Case 2: Directed Multigraphs (Allow Multiedges) #

If we allow multiple edges between the same pair of vertices, then the edge set can absolutely be uncountable.

A straightforward example:

• Let ( V ) be a singleton set ( {v_1} ) (which is trivially countable).
• Now add an uncountable number of loop edges (edges from ( v_1 ) to ( v_1 )). Each of these edges is a distinct element of ( A ), making ( A ) an uncountable set.

Quick Summary #

• For simple directed graphs: Edge set ( A ) is at most countable.
• For directed multigraphs: Edge set ( A ) can be uncountable—it all depends on how many multiedges we allow between vertex pairs.

内容的提问来源于stack exchange，提问作者Mr.M