💡 Let $G=(V,E)$ be a graph. $G$ is called connected if it holds for all $u,v\in V,u\ne v$ that: there exists a $u$-$v$-path in $G$.

💡 A graph $G=(V,E)$ is called $k$-connected when:

• $|V|\ge k+1$ and
• $G[V\setminus X]$ is a connected graph $\forall X\subseteq V$ with $|X|<k$

i.e., one has to remove at least $k$ vertices (and adjacent edges) in order to turn the graph into a disconnected graph.

💡 If $G$ contains a vertex $u$ with degree $\text{deg}(u)<k$, then $G$ is not $k$-connected.

📖 Menger’s Theorem (Vertices):

Let $G=(V,E)$ be a graph. Then it holds that $G$ is $k$-connected if and only if $\forall u,v\in V,u\ne v$ there exist $k$ disjoint $u$-$v$-paths.

💡 Let $G=(V,E)$ be a graph. $G$ is called $k$-edge-connected when:

• $(V,E\setminus X)$ is connected $\forall X\subseteq E$ with $|X|<k$

📖 Menger’s Theorem (Edges):

Let $G=(V,E)$ be a graph. Then it holds that $G$ is $k$-edge-connected if and only if $\forall u,v\in V,u\ne v$ there exist $k$ edge-disjoint $u$-$v$-paths.

💡 It always holds that:

$$\text{Vertex Connectivity}\le \text{Edge Connectivity}\le \text{Minimum Vertex-Degree}$$

💡 Let $G=(V,E)$ be a connected graph. A vertex $v\in V$ is called a cut vertex if and only if $G[V\setminus \{v\}]$ is disconnected.

💡 Let $G=(V,E)$ be a connected graph. An edge $e\in E$ is called a cut edge if and only if $G-e$ is not connected.

📌 Let $G=(V,E)$ be a connected graph. If $(x,y)\in E$ is a cut edge then it holds that: $\text{deg}(x)=1$ or $x$ is a cut vertex, and analogously for $y$. Note that this does not hold in the other direction for the general case.

💡 Let $G=(V,E)$ be a graph. We define an equivalence relation on $E$ by

$$e\sim f⟺\{\begin{array}{l}e=f,\text{or}\\ \exists \text{cycle through e and f}\end{array}$$

The equivalence classes will be called blocks.

📌 Two blocks intersect, if at all, always in a cut vertex.

💡 Let $G=(V,E)$ be a graph. A Hamiltonian cycle is a cycle in $G$ that contains every vertex $v\in V$ exactly once. A Eulerian tour is a closed walk in $G$ that contains every edge $(u,v)\in E$ exactly once. If a graph contains a Hamiltonian cycle the graph is called hamiltonian.

📖 A connected graph $G=(V,E)$ contains a Eulerian tour if and only if the degree $\mathrm{deg}v$ of every vertex $v\in V$ is even. Such a Eulerian tour can be found in $O(|E|)$ if it exists. If a graph contains a Eulerian tour the graph is called Eulerian.

📖 Let $m,n\ge 2$. A $n\times m$ grid contains a Hamiltonian cycle if and only if $n\cdot m$ is even.

📖 A bipartite graph $G=(A\cup B,E)$ with $|A|\ne |B|$ cannot contain a Hamiltonian cycle.

📖 Dirac’s Theorem:

Every graph $G=(V,E)$ with $|V|\ge 3$ and minimum degree $\delta (G)\ge \frac{|V|}{2}$ contains a Hamiltonian cycle.