Graph (discrete mathematics)

Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures.

A directed graph with three vertices and four directed edges (the double arrow represents an edge in each direction)

To avoid ambiguity, this type of object may be called precisely a directed simple graph.

To avoid ambiguity, this type of object may be called precisely a directed multigraph.

Some authors use "oriented graph" to mean the same as "directed graph". Some authors use "oriented graph" to mean any orientation of a given undirected graph or multigraph.

A complete graph with five vertices and ten edges. Each vertex has an edge to every other vertex.

A complete graph is a graph in which each pair of vertices is joined by an edge. A complete graph contains all possible edges.

Most commonly in graph theory it is implied that the graphs discussed are finite. If the graphs are infinite, that is usually specifically stated.

A planar graph is a graph whose vertices and edges can be drawn in a plane such that no two of the edges intersect.

There are several operations that produce new graphs from initial ones, which might be classified into the following categories: