Proving |V(G)|-1 <= |E(G)| for Connected Graphs: Graph Theory Homework Statement

[tgt]

Homework Statement

Show that for any connected graph we have the |V(G)|-1 <= |E(G)|

The Attempt at a Solution

There exists a longest path in the connected graph, call H. It has |E(H)|+1>=|V(H)|. For the other parts of the graph, in order to minimise the number of edges we have all other branches out of this longest path has number of edges equaling number of vertices (any less edges and we have an isolated vertex) hence a connected graph with minimum number of edges must have |V(G)|-1 <= |E(G)|

 

[mistermath]

Have you considered induction?

I'm trying to visually see a connected graph. Say you have 6 vertices (a,b,c,d,e,f), since it it connected, you can "construct it" by say write a on the paper, then write b and put an edge. then write c, and put an edge from either a to c or b to c, and so on.. the one thing that remains invariant is that you need *at least* one edge for each vertex that you add.

I'm sure there might be a more "applied way" like consider connected graph v = {a,b}, e = {(a,b)}, then |v|= 2 and |e| = 1, so |v|-1=|e| this shows that you cannot have |v|-1>|e| "for all connected graphs" since that would contradict your example. Now you have an upper bound. But I don't know where to go from there..