Upper bounds on the average distance \(\overline{l}\) between pairs of vertices of a connected graph with given order \(n\) and minimum degree \(\delta\) are studied. The AutoGraphiX system for conjecture making is used to generate such bounds when the minimum degree is at least 2, 3, 4 or 5. A sharp bound is proved when \(\delta \ge 2\) and conjectures are provided in the remaining three cases. Two more conjectures are given for particular cases, namely, when \(n = (\delta +1)k\) and \(n=(\delta +1)k +2\) for some integer \(k \ge 2\).