Graphs

A graph is a collection of nodes/vertices and edges.
Edges on a graph can be directed or undirected.
Vertices are adjacent if they are connected by an edge.
Edges are incident to a vertex if they are connected to it.
The degree of a vertex is the number of edges connected to it.
A path is a sequence of connected vertices and edges in a graph.
A cycle is a path where the start and end vertices are the same.
An connected, undirected, acyclic graph is a tree.
The sum of the degrees is twice the number of edges.
A subgraph is a graph which contains a subset of the edges and vertices in a graph.
A spanning subgraph is a subgraph which contains all vertices in the original graph.
A forest is a collection of trees.
A spanning tree of a connected graph is a spanning subgraph which is also a tree.

Graph traversals

Depth first search (DFS) is a graph traversal where the graph is traversed as deeply as possible, then across.

Breadth first search (BFS) traverses across a graph, then down.