# Terminology and notation

## 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.