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.