- #1
tgt
- 522
- 2
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)|
Last edited: