Homework Help

Graph theory questionLet  G be a graph with no cycles. Prove that V = E+C where V is...

user profile pic

ashifs | Student, Undergraduate | (Level 1) Honors

Posted November 9, 2011 at 2:55 AM via web

dislike 0 like

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

user profile pic

sciencesolve | Teacher | (Level 3) Educator Emeritus

Posted November 30, 2011 at 1:36 AM (Answer #1)

dislike 0 like

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