Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove that no tree with three or more vertices is a perfect square.

(1)the original tree contains at least one pair of vertices such that with $d(x,y)=2$ Suppose the $G$ contained such a pair, say x,y with vertex z between.Then in $G^2$, x-y would also be connected, so there will be a cycle (xzy).

(2)$d(x,y)=1$ for all vertices. The graph is a complete graph, and the number of edges is $\frac{v}{2}(v-1)$ the only way this could equal $v-1$ is if $v=1,2$, which is disallowed in the assumption.

(3)$d(x,y)=1$ or $d(x,y)=0$ for all vertices The graph contains at least one isolated point, and is disconnected.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.