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.



Asked on

1 Answer | Add Yours

sciencesolve's profile pic

Posted on (Answer #1)

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

We’ve answered 396,728 questions. We can answer yours, too.

Ask a question