Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory

  1. Jun 23, 2008 #1


    User Avatar

    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)|
    Last edited: Jun 23, 2008
  2. jcsd
  3. Jun 23, 2008 #2
    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..
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook