is a scene graph actually a tree? All "scene graphs" I've seen in practice are actually trees, but I have some vague memories about somebody saying a while ago that sometimes they can actually be graphs (technically, trees are already graphs, but you get the point).

If they can actually be graphs, what are some practical examples?

If they're always just trees, is there some history behind why it was originally called "scene graph"?
Yes, scene graphs can be non-tree graphs. Your question is a little vague, but assuming you're talking about something like the scene graph in rendering a frame of video, for say a feature film, then yes, there are often references between objects. For example, in a compositing application, you might have a piece of footage with an effect applied. The effect may have as one of its inputs another piece of footage which is also in the scene. (It might use the other image for blending, as a reflection map, as a diffuse or specular lighting map, a bump map etc.) So you could have a scene that looks like this:

scene contains:
    footage A contains:
        filter "Multiply Blend" which takes input:
            footage B
    footage B
    footage C


In something like a game, you might objects that refer to other objects that they can collide with:

scene contains:
    ground which can collide with:
        player
        ball
        goal
    player which can collide with:
        ground
        ball
        goal
    ball which can collide with:
        player
        ground
        goal


etc.