I am beginning to work through a text in graph theory and have a couple of questions.
1) Can we always assume a graph is nonempty, i.e., if a graph $G$ has order $n$, do we assume $n\in \{1,2,...\}$?
Allowing the empty graph would seem to cause problems with some of the definitions.
2) Mathematical induction seems to be a major proof technique in graph theory. Let's say we're doing induction on the size $n$ of a graph. I often have trouble picking out the $n$ for my base case. Many times if I start at $n=0$ (by (1) should I ever do this?) or $n=1$ the theorem is almost vacuously satisfied, and it feels like I am cheating. Here is an example:
Theorem. Every closed odd walk in a graph contains an odd cycle.
proof. Induction on length of walk.
Base case: $n=1$ is vacuously satisfied (there is no closed walk of length $1$ since we are assuming our graphs are simple). I feel like this is cheating, so I go on to the next case. If $n=3$ then we can easily prove that the walk is a cycle. Now I feel a little better and proceed with the inductive step...
Suppose we have an odd length $n$ walk and the theorem holds for all odd walks of length $<n$. Suppose the walk $v_0,v_1,...,v_n$ begins and ends at $v_{0}=v_{n}$. If no vertices are repeated along the way, we're done. Else, pick the least vertex that is repeated, then pick the max vertex that matches it. Pick the least vertex after this max that is repeated, and then the max vertex that matches it. If we ever get an odd walk in this process, apply the induction hypothesis, and we're done. Otherwise if they are all even, then when we collapse all of these cycles (loops), we get an odd cycle beginning and ending at $v_{0}$ (since an odd number of edges minus a bunch of even numbers is odd).
What is to stop me from using "dumb" base cases?
What text are you using? Doesn't your text say that the vertex set is nonempty? If it doesn't, it should; recognizing the "null graph"" (with no vertices) as a graph is a bad idea. (By the way, the term "empty graph" is often used to mean a graph with no edges)
Your example proof does not use mathematical induction in the form "if $P(n)$ implies $P(n+1)$, and if $P(1)$ holds, then $P(n)$ holds for all $n$. (E.g., how would you prove that a closed walk of length $13$ contains an odd cycle, using only the fact that every closed walk of length $11$ contains an odd cycle?) What you are using is the more general form of induction which goes: "if I can prove $P(n)$ assuming that $P(k)$ holds for all $k\lt n$, then $P(n)$ holds for all n". This form of induction does not require a base case. However, you do need to be careful to make sure that your induction argument works in the smallest cases. E.g., the statement "a closed walk of odd length is either a cycle or else it contains a shorter closed walk" is true even when the given walk is of length $3$, even though no shorter closed walk is possible.