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
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
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.
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:
The generating rules vary depending on the kind of graph.