1
$\begingroup$

I'm having trouble with this question:

Suppose there is a unique path between any pair of vertices in $G$. Prove that $G$ is a tree.

I know that a path is a trail where all vertices are distinct and a tree is a simple connected graph with no circuits.

  • 0
    You need to define a tree since that statement *is* a definition of a tree.2012-11-13

1 Answers 1

3

HINT: Suppose that $G$ is not a tree; then there is a circuit in $G$. Pick two vertices, $u$ and $v$, in this circuit. Now use the circuit to find two different paths between $u$ and $v$.