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.