2
$\begingroup$

Is G necessarily a cycle?
I suspect not but I'm having hard time showing this.

Also,
Let be a tree. Prove that the average degree of a vertex in T is less than 2.
I know that the sum of degrees of all vertices is $2|E|=2|V|-2$. Thus the graph must be connected, and the average degrees of a vertex is less than 2, so the vertices must be a degree of one. Is this correct?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

1) No. Just take two triangles.

If $G$ is connected and every vertex has degree $2$ then $G$ is a cycle.

2) Combine sum of degrees formula with tree formula...

$\endgroup$
2
$\begingroup$

If $G$ is finite, then it must contain a cycle. Start at any vertex, and follow the edges. Eventually you'll run out of new vertices, and have to visit one you've been to before. But they all have degree 2, so it must be the starting vertex.

For the second question (and normally one asks only one question at a time here), try counting the number of edges in a tree; surprisingly, it depends only on the number of vertices and not on the shape of the tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.