Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From this graph theory lesson :

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 ?

share|cite|improve this question
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
up vote 3 down vote accepted

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

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

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.