the latter case, the two edges $\{v_i,v_j\}$ and $\{v_i,v_k\}$ are included in the subgraph. Hence, all included vertices have degree two. By the defining property of a transversal, all selected edges have different colors, so the subgraph is really rainbow, and there are no cycles of length two. Moreover, for every vertex $v_i$, we have $A_{i,i}=n$, so at most one vertex does not belong to the subgraph.

Thesis structure
----------------

In Chapter 2, some results on rainbow paths are proved; in particular, we prove Theorem \[thm:intro\]. The chapter also contains an informal overview over the ideas used in the proof.

Chapter 3 takes a look at $k$-rainbow paths. It is proved that every proper edge coloring of $K_n$ contains a $k$-rainbow path on at least $(1-2/(k+2)!)n$ vertices.

The final chapter is a short conclusion.

Notation
--------

In this section, we define the notation used throughout the thesis and briefly introduce the basic graph-theoretic notions.

### Sets

We write ${\mathbold{N}}$ for the set $\{1,2,3,\dotsc\}$ of natural numbers. If $n$ is a natural number, then we write $[n]$ for the set $\{1,2,\dotsc,n\}$.

We use capital letters for sets. If $A$ is a set, then $\abs{A}$ is the cardinality of $A$ and $\binom{A}{k}$ 