Yes. If Knuth wasn't making stuff up then you can find some historic accounts (1300s-1500s) in "Two Thousand Years of Combinatorics."
More recently, Euler's paper in 1736 didn't have what you'd recognize as a modern graph diagram, Konig's textbook in 1936 did, and the papers developing the subject between those dates eventually used the modern notion of lines connecting dots as a way to represent edges and nodes.
Yes, your second paragraph was basically what I thought was the case, it does seem quite recent. I don't have access to the Knuth article, I'd love to know what he means. Ramon Llull maybe?
More recently, Euler's paper in 1736 didn't have what you'd recognize as a modern graph diagram, Konig's textbook in 1936 did, and the papers developing the subject between those dates eventually used the modern notion of lines connecting dots as a way to represent edges and nodes.