Graphs are studied in graph theory, a part of discrete mathematics. A graph data structure consists of a finite set of two types of objects:

• nodes or vertices
• edges or lines, which are related pairs of nodes

The formal, mathematical definition for a graph is just this: G = (V, E). This means a graph is an ordered pair of a finite set of vertices and a finite set of edges.

If all edges within a graph are bidirectional, the graph is undirected. A simple, undirected graph is shown as follows:

This graph consists of four nodes and four edges. The set of nodes and edges can be represented with a formula similar to the following:

Curly braces mean unordered pairs (it is possible to travel from one node to another in both directions). {0,2} is the same as {2,0}.

In case of a directed graph (digraph), edges can go only in one way:

Nodes and edges can have names and properties. A graph model that supports properties is an extension of the graphs from the graph theory, and this is called the property graph model. Both nodes and edges can have names (labels for nodes and types for relationships), as shown in the following figure:

This is a digraph, and you can see four nodes representing four instances of the Person entity and a node representing the Book entity with their names (or labels), and additional key/value pairs of properties. There are two different edge types representing two relations between the persons and the book entity. All edges are directed.

A graph model can be extended by assigning a weight to edges. Such a graph is called a weighted graph, and usually represents structures where relations between nodes have numerical values, such as the length of a road network.

The following figure shows a simple weighted graph:

As you can see, four nodes represent cities with the distance in kilometers between them. It can be used to find the shortest route between two cities.

Graphs are useful for representing real-world data. There are many useful operations and analyses that can be applied.