This note assumes that all graphs are simple, i.e. there is no case where a vertex $v$ is adjacent to itself (no loops) nor that any other vertex $u$ has more than one edge incident to $v$ (no multiple edges). Unless noted otherwise, assume everything concerns undirected graphs.
A graph $G$ is defined by a set of vertices $V$ and set of edges $E$.
Vertices. In an undirected graph, the degree of a vertex $v$ is the number of vertices it is adjacent to. In a directed graph, the in-degree of $v$ is the number of edges pointing to $v$ and the out-degree of $v$ is the number of edges pointing from $v$.
Edges. In an undirected graph, an edge $e$ is said to be incident on $u$ and $v$ if $\{u, v\} \in E$ or, in a directed graph, $(u, v) \in E \vee(v, u) \in E$.
<aside> đź’ˇ
A graph $G$ is said to be connected if there is a path between any 2 distinct vertices. A connected component of $G$ is a set of vertices that are connected by a path. The following holds for all undirected graphs.
</aside>
<aside> đź’ˇ
A cut of a graph $G$ is a set of vertices $S$ removed from $V$. The size of a cut, instead of being $|S|$, is the number of edges incident on elements of $S$ and $V \setminus S$ (i.e. edges removed).
</aside>
The following holds for all finite, undirected graphs.
$$ \textbf{Handshaking Lemma} \\ \sum_{v_i \in V} \deg(v_i) = 2 |E| $$
Many graph proofs depend entirely on induction. Buildup error occurs when, in the inductive step, a property that holds for a smaller graph is asserted to hold by constructing a larger graph. The error comes from the fact that it is not necessarily true that any graph of size $n+1$ with some property can be “built up” from any graph of size $n$ with the same property. The proper way to approach the inductive step is to use the shrink down, grow up approach.
$1. \space$Start with a size $n + 1$ graph and shrink down to the size $n$ graph.
$2. \space$Apply the inductive hypothesis to the size $n$ graph.
$3. \space$Grow up to the size $n+1$ and show that the same property holds for all cases.