0
$\begingroup$

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 ?

  • 0
    @MarianoSuárez-Alvarez: I didn't downvote because the definition he copied excluded $V=\emptyset$ but because his question about $E=\emptyset$ is answered in the source immediateyl after the definition2012-09-24

2 Answers 2

3

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

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

  • 1
    Or a hard-wired network after someone snips the cables.2012-09-19
1

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.