Welcome to our community

Be a part of something great, join today!

Degrees of Vertices IV

Joystar1977

Active member
Jul 24, 2013
119
Let G be a graph with vertex set V = {v1, v2, v3, v4, v5}.

If the degrees of the vertices are 1, 2, 1, 3, 1, respectively, is G a tree? Why or why not?

2E = deg v1 + deg v2 + deg v3 + deg v4 + deg v5

2E = 1 + 2 + 1 + 3 + 1

2E = 8

E = 4

Yes, the degrees of vertices 1, 2, 1, 3, 1, G is a tree because the number of edges should be n-1 where n is the number of vertices.

Is this correct?
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
Let G be a graph with vertex set V = {v1, v2, v3, v4, v5}.

If the degrees of the vertices are 1, 2, 1, 3, 1, respectively, is G a tree? Why or why not?

2E = deg v1 + deg v2 + deg v3 + deg v4 + deg v5

2E = 1 + 2 + 1 + 3 + 1

2E = 8

E = 4

Yes, the degrees of vertices 1, 2, 1, 3, 1, G is a tree because the number of edges should be n-1 where n is the number of vertices.

Is this correct?
Not bad. But you also need to show that $G$ is a connected graph. There can exist a graph on $n$ vertices which is disconnected (thus not a tree) and has $n-1$ edges. So just by virtue of having $n-1$ edges a graph doesn't become a tree. It needs to be connected too.
 

Joystar1977

Active member
Jul 24, 2013
119
Thank you Caffeinemachine!