Determining on whether topology is a tree or a hypercube
As you have noticed, a simple solution is to generate a token at the initiator and then forward the token through the network using a DFS strategy.

If this token encounters a node that is a leaf, the node will record this information in the token before it is sent back. So when the token has completed the DFS, it will have returned to the initiator who then inspects the token to check if it has encountered any leaf.

The O(m) message complexity follows from the message complexity of DFS, and to show this it's sufficient to prove that the token is sent a constant number of times over each edge.