Better Students Ask More Questions.
Graph theory questionLet G be a graph with no cycles. Prove that V = E+C where V is...
1 Answer | add yours
To prove this formula, you must prove the Euler's formula.
Remember which is the Euler's characteristic for connected planar graphs:
`chi` = V-E+F
F is the number of faces in the graph
V - vertices of the graph
In case of any planar connected graph, chi = 2. This value is similar to Euler's polyhedron formula for the surfaces of any polyhedron.
Using induction on the number of faces in the graph => V = E-F+C+1.
C is the number of components of the graph.
For a tree graph, F=1 => V = E+C
Posted by sciencesolve on November 30, 2011 at 1:36 AM (Answer #1)
Join to answer this question
Join a community of thousands of dedicated teachers and students.