graph + tree

• Jul 4th 2010, 09:35 PM
dunsta
graph + tree
If a graph has
8 verticies:
2 with 1 degree
1 with 2 degrees
5 with 3 degrees.

If it is not a tree I must prove why.

The only way I can think of to do this is to draw the graph (which I can't replicate here).
When I draw the graph I find I have 2 non-trivial circuits, therefore the graph is not a tree.
Is this the only way to prove the graph is not a tree?
• Jul 4th 2010, 09:51 PM
pickslides
For your graph to be a tree then $\epsilon = v-1$ where $\epsilon$ = number of edges and v = number of vertices which is given to be 8.

To check you need to find the number of edges. $\epsilon = \frac{1}{2}\sum d(v)$ where $d(v)$ is the degree of each vertex. Does this equal $8-1 = 7$ ?
• Jul 4th 2010, 10:17 PM
dunsta
ok,
I understand that the edges = vertices -1 for a tree.
So for 8 vertices there should be 7 edges.

(I can draw this, bu t I get non-trivial circuits. Therefore not a tree)

But to prove it, I use

edge = vertices - 1.
edge = $\frac{1}{2} *$ v1 degrees + v2 degrees... vn degrees

edge = 7
edge = 0.5 * (1+1+2+3+3+3+3+3)
= 0.5 * 19
= 9.5

7 != 9.5, therefore not a tree.

correct?

btw, thanks for taking the time to help pickslides.
• Jul 4th 2010, 11:27 PM
pickslides
looks good to me.