So my problem is proving that the max degree of the simple graph is less than the number of its vertexs.
Without using induction,this can be simply proved like this:
Suppose that the vertex X has max degree which is n,so there must be at least n vertexs.Plus the x itself,there must be n+1 vertexs.And we could say the max degree of the simple graph(which is n) is less than the number of its vertexs(which is n+1)
Since the question needs a complete reasoning process,I think maybe I could use induction to prove this.So here is my process:
1.The basic step.When there is only 1 vertex,its max vertex is 0,which is surely less than the number of vertex 1
2.The induction step.Suppose when there is k vertexs,the conclusion still be tenable.
3.The last step.Now consider when there is k+1 vertexs,and the max degree is d.and we remove one vertex from the original graph G.After that,the G turns to G',and the max degree turns to d'.Consider 2 conditions:
3.1
The removed vertex didn't influence the max degree of the graph at all(eg,the removed vertex is not the vertex that has max degree in the G).So for G',its max degree is still d(d=d').According to the second step,since the G' has only k vertexs now,d must be less than k.And because k<k+1,we have d<k+1.
3.2
The removed vertex is exactly the vertex that has max degree in the original graph G.Here I feel confused as I can't figure out how to prove that d<k+1.After I add back the removed vertex,the max degree turns to d again.And I can only conclude d'<d and d'<k.These seems no help for the solution.
So when the reasoning process go to 3.2,how should I do next?
For $n=1$, the max degree of a vertex of a graph on $n$ vertices is clearly $0=n-1$. Now assume that $\max\{\deg v:v\in V_n\} \leqslant n-1$ for some $n\geqslant 1$. Then $$\max\{\deg v: v\in V_{n+1}\} \leqslant \max\{\max\{\deg v:v\in V_n\} + 1, n\} = \max\{(n-1)+1, n\} = n, $$thus proving the inductive step. The claim then follows for all positive integers $n$.