Show that if G is a connected graph of order p then the size

Show that if G is a connected graph of order p, then the size of G is at least p1.

prove by induction

if the order is 2

it must have one edge for the graph to be connected.

induction hypothesis for p <= K , statement is true

For P = K+1

graph has K+1 vertices

Suppose statement is not true i.e. graph is connected but the size is less than p-1 = K

Since the vertices are K+1 there must be some vertex with degree <=1

otherwise Assuming every vertex has degree atleast 2 then

number of edges would be greater or equal to 2* K+1/2 = K+1

which is not true

So cnsider a vertex with degree < = 1

remove that vertex now the remaining graph is connected and has K vertices

and by induction hypothesis it has atleast K-1 edges

and now to put the remaining vertex we must have at least one edge

So size of graph is atleast K