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

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

### Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes