Most people cite Euler's 1741 "Bridges of Königsburg" paper as the oldest graph algorithm. Unfortuantely, Euler doesn't actually describe his algorithm in detail, but only gives a half-hearted example:
“When it has been determined that such a journey can be made, one
still has to find how it should be arranged. For this I use the
following rule: let those pairs of bridges which lead from one area to
another be mentally removed, thereby considerably reducing the number
of bridges; it is then an easy task to construct the required route
across the remaining bridges. and the bridges which have been removed
will not significantly alter the route found, as will become clear
after a little thought. I do not therefore think it worthwhile to give
any further details concerning the finding of the routes.”
The first complete proof that all even connected graphs have Eulerian tours is apparently due to Heirholzer more than a century later.
Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae 8:128–140, 1741. Presented to the St. Petersburg Academy on August 26, 1735. Reprinted in Opera Omnia 1(7):1–10.
Carl Hierholzer. Über die Möglichkeit, einen Linienzug Ohne Wiederholung und ohne Unterbrechnung zu umfahren. Mathematische Annalen 6:30–32, 1873.