graph-theory-one-page

Basics
A graph is a set, V, of objects called vertices and set, E, of unordered pairs, (a,b) of elements of V called edges.

\$V={a, b, c, d}; E={(a,b), (b,c), (a,d). (d,b) }\$

If more than one edge connects two vertices it is called a multi-edge.

If an edge connects a vertex to itself, it is called a loop or self-edge.

A graph with no multi-edges and no loops is a simple graph.

A complete graph is one in which every pair of vertices is connected by an edge.

Edges can be directed or undirected. In a directed graph, also known as a digraph, the edges are ordered pairs — the edge from a to b being distinct from the edge from b to a.

The degree of a vertex is the number of edges that end at that vertex. In a directed graph we distinguish in-degree and out-degree.

A path is a sequence of consecutive edges. The length of the path is the number of edges.

A circuit is a path that starts and ends at the same vertex.

A bipartite or two-mode graph is one with two kinds of vertices such every edge connects a vertex of one type to a vertex of the other type.

A graph is called connected if there is a path between every pair of vertices in the graph. A graph that is not connected can be separated into connected components.

Vertices are also called nodes. Edges are also called ties, links, connections.