# What is the most basic graph, and how would you use it in an induction-proof?

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

-
Depends on the problem. There's no "one" basic graph that is used in all induction proofs. But, a single vertex (with no edges) is a graph. And, sometimes people talk about the graph with no vertices and no edges. –  Graphth Apr 24 '12 at 20:27
By the way, you don't need to use the (homework) tag when the question you're actually asking is not the one in your homework. That is, if even a complete, detailed answer to your MSE question wouldn't be something you could turn in as a solution to your homework, then you don't need the tag. –  Henning Makholm Apr 24 '12 at 20:37
Obligatory link –  Chris Eagle Apr 24 '12 at 20:47
@ChrisEagle - :) An insider math-joke(or no?) ilike it –  Adel Apr 24 '12 at 20:48
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. –  Adel Apr 24 '12 at 20:49

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.

-
Thanks, this helps very much. I need to apply this to the question: "prove that every connected graph has a spanning tree" and start with a connected graph " –  Adel Apr 24 '12 at 20:32
Then the one-vertex graph would indeed be a good base case. The empty set of edges ought to satisfy your definition of a spanning tree for it. –  Henning Makholm Apr 24 '12 at 20:35
If that's what you're attempting to prove, there is a much easier way to do so without using induction. Recall that every edge in a tree is a bridge but connected graphs don't necessarily satisfy this condition, that is, they contain non-bridge edges. What can you do to the connected graph to make it into a spanning tree? –  chris Apr 24 '12 at 22:20
@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...) –  Henning Makholm Apr 24 '12 at 22:49

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.

-
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. –  Kaz Apr 25 '12 at 0:06