Let $G=(V,E)$ be a graph

Handshake Lemma (HL)

• $G=(V,E)$
• $|S|=\sum _{v\in V}deg(v)=2\cdot |E|$
  • sum of the degrees of all vertices is twice the number of edges

Handshake Lemma Corollary

• $G=(V,E)$
• $G$ has an even number of vertices of odd degree

Pairwise Disjoint

• a set of graphs $A_1,A_2,\dots ,A_k$ is called pairwise disjoint if
  • for any pair of graphs $A_i,A_j$, $j,i\in [1,k],j\ne i$ $\to A_i\cap A_j=\varnothing$
• i.e. none of these graphs share any elements ()

Completeness

• complete graph
  • $Kv=(V,E)$ where $E$ contains all two element subsets of $V$
  • no way to introduce a new edge
  • $|E|=\frac{z(z-1)}{2}=(\genfrac{}{}{0ex}{}{z}{{}_2})$

Degree sequence

• degree sequence
  • multiset of degrees of the vertices of G
  • typically represented as a sequence of |V| integers sorted into weakly decreasing order

Reachability

• For vertices $v,u\in V$ we say that $u$ is reachable from $v$ if there exists a walk from $u$ to $v.$
• Reachability is an equivalence relation (reflexive, symmetric, transitive)
• $C(G)$ = number of connected components
  • disjoint non-empty sets of vertices such that in each component all vertices are reachable from each other
  • If $C(G)=1$ we say $G$ is connected

Neighbours

two vertices $v,w$ are adjacent/neighbours

• if $\{v,w\}\in E$ is an edge in $G$
• $vw\to$ notation for $\{v,w\}$

Neighbourhood

• neighbourhood of a vertex $v\in V$ is the set $N(v)=\{w\in V:vw\in E\}$

Incident

a vertex $v\in V$ is incident with some edge $e\in E$ if $v\in e$

1. ends
   - the two ends of some edge $e\in E$ if $v\in e$
2. degree
   - the number of edges incident with it
   - $deg(v)=|\{e\in E:v\in e\}|=|N(v)|$
3. regular
   - $G$ is regular if all of its vertices have the same degree
   - we call a regular graph with all vertices of degree d: d-regular