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


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

Browse other questions tagged or ask your own question.