There are a lot of definitions to keep track of in graph theory. Here is a glossary of the terms we have already used and will soon encounter.
A collection of vertices, some of which are connected by edges. More precisely, a pair of sets \(V\) and \(E\) where \(V\) is a set of vertices and \(E\) is a set of 2-element subsets of \(V\text{.}\)
Two vertices are adjacent if they are connected by an edge. Two edges are adjacent if they share a vertex.
A graph for which it is possible to divide the vertices into two disjoint sets such that there are no edges between any two vertices in the same set.
A bipartite graph for which every vertex in the first set is adjacent to every vertex in the second set.
A graph in which every pair of vertices is adjacent.
A graph is connected if there is a path from any vertex to any other vertex.
The minimum number of colors required in a proper vertex coloring of the graph.
A path (see below) that starts and stops at the same vertex, but contains no other repeated vertices.
The number of edges incident to a vertex.
A walk which uses each edge exactly once.
An Euler path which starts and stops at the same vertex.
A multigraph is just like a graph but can contain multiple edges between two vertices as well as single edge loops (that is an edge from a vertex to itself).
A path is a walk that doesn't repeat any vertices (or edges) except perhaps the first and last. If a path starts and ends at the same vertex, it is called a cycle.
A graph which can be drawn (in the plane) without any edges crossing.
We say that \(H\) is a subgraph of \(G\) if every vertex and edge of \(H\) is also a vertex or edge of \(G\text{.}\) We say \(H\) is an induced subgraph of \(G\) if every vertex of \(H\) is a vertex of \(G\) and each pair of vertices in \(H\) are adjacent in \(H\) if and only if they are adjacent in \(G\text{.}\)
A connected graph with no cycles. (If we remove the requirement that the graph is connected, the graph is called a forest.) The vertices in a tree with degree 1 are called leaves.
An assignment of colors to each of the vertices of a graph. A vertex coloring is proper if adjacent vertices are always colored differently.
A sequence of vertices such that consecutive vertices (in the sequence) are adjacent (in the graph). A walk in which no edge is repeated is called a trail, and a trail in which no vertex is repeated (except possibly the first and last) is called a path.