Graph theory

A graph consists of vertices (points) joined by edges (lines). Two vertices joined by an edge are adjacent. The degree of a vertex is the number of edges incident to it. Every edge contributes exactly $2$ to the sum of all vertex degrees, so $\sum \mathrm{deg}(v)=2|E|$. A path is a sequence of adjacent vertices; a cycle is a path that starts and ends at the same vertex. A graph is connected if there is a path between every pair of vertices. A tree is a connected graph with no cycles. In any tree, the number of edges is exactly one less than the number of vertices: $|E|=|V|-1$.