# Confusion about the definition of graphs

A graph is a non-empty finite set $V$ of elements called vertices together with a possibly empty set $E$ of pairs of vertices called edges. Here are a few examples of graphs:

1. Vertex set $V = \{a, b, c, d\}$ and edge set $E = \{(a, b), (b, d)\}$
2. Vertex set $V = \{1, 2, 3, 4\}$ and edge set $E = \{(2, 4)\}$
3. Vertex set $V = \{wolf, goat, cabbage\}$ and edge set $E = \{(wolf, cabbage)\}$
4. Vertex set $V = \{A, B, C\}$ and edge set $E = \emptyset$.

Is this the correct definition for graphs ? If the graph has possibly empty empty edges how can it be represented diagramatically ? What can be a practical example of a graph where there are no edges at all ?

-
It is weird to not allow empty graphs but to allow at the same time empty edge sets! – Mariano Suárez-Alvarez Sep 19 '12 at 6:20
It is a correct definition of a simple graph. A graph with no edges can be represented diagrammatically as a finite set of points. Pick just about any application and ask yourself what a graph with no edges would represent; in most cases it will be something meaningful. (And in any case they’re very useful within graph theory.) – Brian M. Scott Sep 19 '12 at 6:20
$V$ does not have to be finite, in general – Belgi Sep 19 '12 at 6:22
If you had read a few more sentences in that web lesson, you would have stumbled over a Java Web Start Application that specifically deals with the concept of null graphs, i.e. graphs with $E=\emptyset$. (That's why I downvote). – Hagen von Eitzen Sep 19 '12 at 6:34
@Hagen: didn't the OP actually copy the definition from that lesson? i imagine the restriction to non-empty vertex sets is not his idea... In that case, downvoting because he is faithful to the source he is getting this from is strange. – Mariano Suárez-Alvarez Sep 19 '12 at 6:36

Just a bunch of vertices with no edges connecting them. Dots.

An example might be islands. Or a collection of social hermits.

-
Or a hard-wired network after someone snips the cables. – Brian M. Scott Sep 19 '12 at 6:22

It is not a correct definition of a simple graph. A pair $(a,b)$ is different from the pair $(b,a)$, but a simple graph does not have two edges with the same ends. It is not incorrect, but maybe unusual, to disallow empty and infinite vertex sets.

It would be a correct definition of a non-empty finite directed graph, in which case each arc (edge) has an initial and a terminal vertex, so the ordered pair notation $(a,b)$ can be used here. Simple graphs do not have edges with directions.

Graphs with no edges are frequently used, in particular as starting points for processes. Example: a commonly used model for a random graph requires you to start from a graph with n vertices and no edges, then add one new edge at a time randomly between vertices not yet connected, until you have reached the desired number of edges. It would be awkward if the initial graph of this process is not allowed.

-