When most readers hear the word graph they probably think of a bar chart, a histogram or some visual abomination that is supposed to resemble a pie.
In math terms, a graph is often an abstract way of showing several objects, and the relationships between them.
This is a very general definition. Graphs are used a lot in maths to model a diverse range of things such as social networks, organisation charts, and logistical routes. (And code repositories!)
In games, they are most commonly used to model the locations or screens in a videogame, and how to travel between those places.
This is Level-1 from the NES classic The Legend of Zelda:
And here is that same information in graph form:
Here, the individual rooms are represented by dots called nodes, and the lines between the nodes show that you can travel directly between the two rooms represented by the nodes. These connecting lines are usually called arcs.
I’ve labelled some nodes with the treasures of points of interest contained within those rooms, and I’ve labelled one arc as a dotted line to indicate a special type of travel (going underground) as it is a special case.
Graphs are a useful tool to model relationships between objects in your game. Graphs also have many provable properties that you can exploit to learn more about your own systems or design them to have specific features.
If you fancy making your own try GeoGebra and try modelling your favourite dungeons (or the Sphere Grid from Final Fantasy X. Your choice!)
EDIT: Thanks to @the_exp for spotting a mistake on my graph!