1
$\begingroup$

So, I was looking at some graph theoretical stuff, more specifically Topological Graph Theory, and I had a question about the definition of graphs: is there usually a condition in the definition limiting the number of vertices? Perhaps that the set of Vertices is countable? or even finite? If not, is such a condition commonly put on the set of edges? I was thinking about this, and I believe if there is no condition you can get graphs which act MUCH differently than finite graphs. Any help would be appreciated. Thanks in advance.

  • 0
    @ashley: when people say "$A$ is bounded by $B$" I generally take that to mean "$A \le B$" which is not true in this case. Perhaps you mean "$A$ is controlled by $B$" here. – 2012-12-22

2 Answers 2

3

In some parts of graph theory people probably typically restrict their attention to finite graphs. In other parts there's no reason to do this. For example, Ramsey theory frequently deals with infinite graphs. It's also natural to use countable Cayley graphs in geometric group theory.

The Rado graph is a specific example of an interesting infinite graph.

2

In full generality, if $S$ is a set, then we can define graphs with the vertex set $S$ (such as the complete graph). Many important mathematical objects can be rephrased as graphs (functions, relations, etc.), so you've probably encountered graphs with an uncountable number of vertices this way.

A famous graph theory problem where an uncountable number of vertices arises is the chromatic number of the plane:

In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance 1 from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 4, 5, 6 or 7. The correct value may actually depend on the choice of axioms for set theory (Shelah & Soifer 2003).

[emphasis mine]

We see that properties of graphs with an uncountable number of vertices may have behaviour different from graphs with a finite or countable number of vertices. Whether or not you want to work with such graphs is more of a matter of personal taste, than of any inherent barrier in graph theory.