Terminology and notation

Basics of Graphs

A graph is a collection of points (called vertices) and lines connecting those vertices (called edges).
Graphs can be directed (edges have a direction) or undirected (edges do not have a direction).
The degree of a vertex is the number of edges touching it. In a directed graph, we distinguish between the in-degree (number of edges coming in) and out-degree (number of edges going out).
A loop is an edge that starts and finishes at the same vertex.
A simple graph is a graph with no loops or repeated edges.
A graph is connected if there is a path from every vertex to every other vertex.

Graph Notation

The order of a graph, denoted as G , is the number of vertices it contains.
The size of a graph, denoted as G , is the number of edges it contains.
We often denote a graph as G(V, E), where V is the set of vertices and E is the set of edges.
A subgraph H(V’, E’) of G(V, E) has V’ as a subset of V and E’ as a subset of E.
A complete graph on n vertices, denoted by K_n, is a simple graph with an edge between every distinct pair of vertices.

Trees and Forests

A tree is a connected graph with no cycles.
A forest is a graph without cycles, but it might not be connected — it could be a collection of several disjoint trees.
A vertex of degree 1 in a tree or forest is called a leaf.
Every tree with two or more vertices has at least two leaves.

Paths and Cycles

A path in a graph is a sequence of unique vertices in which successive vertices are connected by edges.
A cycle is a path that starts and ends at the same vertex, with no other repeated vertices or edges.
A graph is cyclic if it contains at least one cycle, and acyclic if it contains no cycles.
A Hamiltonian cycle is a cycle that visits each vertex exactly once (not including the starting and ending vertex, which are the same). A graph containing a Hamiltonian cycle is called a Hamiltonian graph.
An Eulerian cycle is a cycle that includes each edge exactly once. A graph is Eulerian if it contains an Eulerian cycle.