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.
