# Discrete Mathematics

posted by .

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?

• Discrete Mathematics -

By definition, a tree is a connected acyaclic graph.

One of the sufficient properties of a tree is that the number of edges equals the number of vertices minus one.

Note: number of edges = (sum of degrees of all vertices)/2.

• Discrete Mathematics -

MathMate: Thank you!

## Similar Questions

1. ### Math

Prove that a simple graph with n >_ 2 vertices must have atleast two vertices with the same degree. There was a hint given in the book saying that the key to this is the graph can not have both a vertex of 0 degree and a vertex …
2. ### Math

Prove that a simple graph with n >_ 2 vertices must have atleast two vertices with the same degree. There was a hint given in the book saying that the key to this is the graph can not have both a vertex of 0 degree and a vertex …
3. ### heelp math

A graph is constructed iteratively according to the following algorithm. The graph starts as a single vertex. With probability p, the graph stops here. Otherwise, 3 new vertices are constructed and joined to this vertex. If we have …
4. ### Discrete Mathematics

Let G be a graph with vertex set V = {v1, v2, v3, v4, v5}. A. Is it possible for the degrees of the vertices to be 3, 6, 2, 1, 5, respectively?
5. ### Discrete Mathematics

Using Fleury's Algorithm in the graph to the bottom left, I deleted three edges and I got the graph to the bottom right. If I am currently at the starred vertex, list all possibilities for the edge I should travel next.
6. ### Discrete Mathematics

Let G be a graph with vertex set V = { v1, v2, v3, v4, v5}. Is it possible for the degrees of the vertices to be 3, 6, 2, 1, 5, respectively?
7. ### Discrete Mathematics

Let G be a graph with vertex set V = {v1, v2, v3, v4, v5}. If the degrees of the vertices are 1, 2, 3, 4, 6, respectively, how many edges are in G?
8. ### Discrete Mathematics

Let G be a graph with the vertex set V = {v1, v2, v3, v4, v5}. If the degrees of the vertices are 5, 1, 0, 6, 2, respectively, does G have an Eulerian path?
9. ### Discrete Mathematics

Using Fleury's Algorithm in the graph to the bottom left, I deleted three edges and I got the graph to the bottom right. If I am currently at the starred vertex, list all possibilities for the edge I should travel next.
10. ### Discrete math

please help I'm completely lost Is the following connected graph a tree please explain There are 4 vertices, two with degree 1, one with degree 2, and the degree of the fourth vertex is not known.

More Similar Questions

Post a New Question