# 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$

## 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)$:

1. $E_1 \subseteq E$ and $V_1 \subseteq V$ such that for all $e \in E_1, \gamma(e) \subseteq V_1$
2. $\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:

1. For all $i = 1, ..., k - 1$: $v_i$, $v_{i+1}$ are the endpoints of $e_i$
2. 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.

1. Start on a vertex with on odd degree. If no such vertex exsists start at an arbitrary vertex.
2. Add any adjacent vertex that is not a bridge / that doesn't cause the graph to become disconnected
3. Remove the added edge from the graph
4. 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.