Graph theory question
Let G be a graph with no cycles. Prove that
V = E+C where V is the number of verticies, E is the number of edges
and C is the number of components of the graph.
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
Join to answer this question
Join a community of thousands of dedicated teachers and students.Join eNotes