# Graphs

**(Undirected) graph: $(V, E, \gamma)$**

- Set $V$ of vertices,
**Isolated**: vertex without neighbors**Degree $deg(v)$**: numer of times a vertex occurs as endpoint

- Set $E$ of edges
- Function $\gamma(e) = \{v, w\}$, that maps each edge $e$ to its endpoints $v, w$
- $V$ and $w$ are
**adjacent**/**neighbors** - $V$ and $e$ are
**incident** **(self-)loop**if $v = w$

- $V$ and $w$ are

## Graph properties #

**Multi-graph**: if $\gamma$ is**not**injective (two edges have the same endpoints / parallel edges)**Simple**: if $\gamma$ is injective**Connected**: if there exsists a path from any vertex to any other vertex (otherwise**disconnected**)**Components**: connected pieces in a disconnected graph**Bridge**: an edge in a connected graph if removing it makes the graph disconnected

## Special graphs #

**Discrete graph $U_n$**: has $n$ vertices, but to edges (disconnected dots)**Complete graph $K_n$**: has $n$ vertices and all distinct vertices are connected by a single edge**Regular**: if all vertices have the same degree**Linear graph $L_n$**: has $n$ vertices and eges (looks like a chain)

$K_n$ and $L_n$ are connected graphs

## Subgraphs #

Intuatively: remove vertices and connected edges

Subgraph $H = (V_1, E_1, \gamma_1)$ is a subgraph of $G = (V, E, \gamma)$:

- $E_1 \subseteq E$ and $V_1 \subseteq V$ such that for all $e \in E_1, \gamma(e) \subseteq V_1$
- $\gamma_1$ is the restriction of $\gamma$ to $E_1$

## Paths in graphs #

**Path**: a pair $\pi = (V_\pi, E_\pi)$ where

- $V_\pi$ is a sequence of vertices
- $E_\pi$ is a sequence of edges

Such that:

- For all $i = 1, ..., k - 1$: $v_i$, $v_{i+1}$ are the endpoints of $e_i$
- No edge occurs more than once in $E_\pi$

### Path properties #

**Circuit**: path that starts and ends in the same vertex**Simple**: path in which no vertex appears more than once (except for the first and last in a**simple circuit**)

## Quotient graphs #

A graph on a equivalence relation R

- Verticies are the equivalence classes of R
- All vertices are connected to each other by an edge in a kind of circle

## Euler paths/circuits #

**Euler path**: visists every edge exactly once**Euler circuit**: euler path that starts and ends at the same vertex

**Theorem on Euler Circuits**:

- If a graph $G$ has a
**vertex of odd degree**that there is**no Euler circuit**in $G$ - If $G$ is connected and $G$ has
**no vertex of odd degree**, then there is an**Euler circuit**in $G$

**Theorem on Euler paths**:

- If a graph $G$ has
**more than two vertices of odd degree**then there can be**no Euler path**in $G$ - If a graph $G$ has
**exactly two vertices of odd degree**then there is an**Euler path**in $G$

## Fleury's algorithm #

Used to find a euler path.

- Start on a vertex with on odd degree. If no such vertex exsists start at an arbitrary vertex.
- Add any adjacent vertex that is not a bridge / that doesn't cause the graph to become disconnected
- Remove the added edge from the graph
- Repeat step 2/3 untill you have covered all edges

## Hamiltonian paths/circuits #

**Hamiltonian path**: visists every vertex exactly once**Hamiltonian circuit**: visists every vertex exactly once except for the first and last vertex**Hamiltonian graph**: if the graph contains a Hamiltonain circuit

**Theorem on Hamiltonian graphs**:

Let $G$ be a connected graph without loops or parralel edges, with $n \leq 3$ vertices and $m$ edges:

- $G$ is Hamiltonian if $deg(v) > n/2$
- $G$ is Hamiltonian if $m \geq \frac{n^2 + 3n + 6}{2}$

Note: there exsist Hamiltonian graphs that do not satisfy the conditions above.