MHB Degrees of Vertices IV: Graph is a Tree?

  • Thread starter Thread starter Joystar77
  • Start date Start date
  • Tags Tags
    Degrees
AI Thread Summary
For the graph G with vertex set V = {v1, v2, v3, v4, v5} and vertex degrees of 1, 2, 1, 3, and 1, the calculation shows that E = 4, which satisfies the condition of having n-1 edges for a tree. However, it is emphasized that G must also be a connected graph to qualify as a tree. A graph can have n-1 edges yet still be disconnected, thus not meeting the criteria for being a tree. Therefore, while the edge count is correct, connectivity must also be established to confirm G as a tree. The discussion highlights the importance of both edge count and connectivity in determining if a graph is a tree.
Joystar77
Messages
122
Reaction score
0
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?
 
Physics news on Phys.org
Joystar1977 said:
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.
 
Thank you Caffeinemachine!
 
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top