Some structured graphs

This section serves two purposes. First we will illustrate that it is non-trivial to prove intuitively true statements. This is indeed the main headache for every graph theory teacher (to convince students that a statement is nontrivial and requires a proof). Indeed, you can ask every teacher, and they have their own stories to share 😁 To see an example, it is typical for a student to write things like "if we have two different paths from $s$ to $t$, then the union of these two paths must contain a cycle" This is indeed true and no matter how you try to draw it, it is trivial! However, writing a formal proof of this fact is not at all trivial (a formal proof would need to identify the sequence of vertices in the cycle). The second purpose is to learn about graphs by working with very specific graphs that can easily be argued about (this is the same principle as when you learn coding by actually solving specific tasks).

📄️ Trees

The following definitions are equivalent:

📄️ Planar graphs

A plane graph is a graph drawn on the plane with curves representing edges and such that these curves do not intersect.