The dependency graph is one of two ways Maya represents your scene (the other being the scene hierarchy). It’s a chain of nodes.
The dependency graph is like a series of instructions describing how to get the current scene starting from scratch: “create a sphere A, move these CVs, create a curve B, project curve B onto sphere A to create curve-on-surface C, trim sphere A using curve on surface C”, and so on.
The dependency graph gets its name from the connections between nodes. In the example above, the project curve operation depends on two inputs: sphere A and curve B.
Each node in the dependency graph represents an action to build up or change the scene, with the final result being the scene in its current state.
As you modify or reshape input objects, change attributes on a node, change node connections, or delete nodes, this graph lets Maya automatically and instantaneously update the entire scene to reflect the changes.
The connections between creation and editing nodes is also called construction history, because it records the history of how the scene was constructed.