Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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...
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.
