(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

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

3. 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)|

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph Theory

**Physics Forums | Science Articles, Homework Help, Discussion**