Does an abstract syntax tree have to be a tree? Does the output of a parser have to be a tree or could it also be general graph?

Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees for their syntax?
The output of a parser need not be a tree. Indeed, when you consider things such as references from the USE of a variable to its DEFinition overlaid on the abstract syntax tree, you immediately have a graph.

The thing is that parsing generally is designed to take place in a single pass – this mattered for historical reasons, such as lack of space and processor speed, but also because it is simpler to reason about. Then subsequent phases decorate the parse tree with additional information.

There are such things as graph grammars, though I don't know whether they are used for parsing programming languages.