0
$\begingroup$

Can a single point be a graph? Or is it just a single edge and two vertices? How do you apply this to an induction-proof in graph-theory?

thanks

  • 1
    from abstract - `The graph with no points and no lines is discussed critically. Arguments for and against its official admittance as a graph are presented. This is accompanied by an extensive survey of the literature. Paradoxical properties of the null-graph are noted. No conclusion is reached.`2012-04-24

2 Answers 2

2

A graph consisting of a single vertex and no edges is perfectly valid, if not very interesting.

It is natural base case to use if you're proving something by induction of the number of vertices in a graph. On the other hand, if you're using induction on the number of edges, the base case needs to be a graph with no edges, but any number (possibly 1) of isolated vertices.

  • 0
    @chris: Formalizing that idea will require induction. (Unless you're imagining something completely gross such as using Zorn's Lemma on the connected sets of edges ordered by reverse inclusion...)2012-04-24
2

The correct "ultimate" base case for a graph is not that of a single vertex, but that of the empty graph: no vertices at all.

If you do not consider this case, you risk making assertions about some property of a graph which does not hold for the empty graph.

A graph may be defined by these rules. A (directed, not necessarily connected) graph is either:

  1. Empty
  2. The result of adding an edge from vertex $a$ to vertex $b$ of a graph (where $a$ and $b$ need not be distinct).
  3. The result of adding a vertex to a graph.

The generating rules vary depending on the kind of graph.

  • 0
    By the way, I wasn't aware that null graph is a controversial animal; but discussions about whether to "allow" it are basically word semantic games which have no effect on the ability to reason about a null graph.2012-04-25