# Graph theory questionLet 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.

*print*Print*list*Cite

### 1 Answer

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

E- edges

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