FoldUnfold Table of Contents Kuratowski's Theorem Kuratowski's Theorem Kuratowski's Theorem is critically important in determining if a graph is planar or not and we state it below. Theorem 1 (Kuratowski's Theorem): A graph is planar if and only if it does not contain any subdivisions of the graphs $K_5$ or $K_{3,3}$. We will not provide a formula proof, however, we will … [Read more...]

## Subdivisions and Contractions

FoldUnfold Table of Contents Subdivisions and Contractions Subdivisions Contractions Subdivisions and Contractions Subdivisions Definition: A Subdivision of a graph $G$ is the addition of a vertex in the middle of any edge of $G$. For example: The graph $H$ is a subdivision of $G$ since $H$ was constructed by adding vertices in between the edges of $G$. This concept of … [Read more...]

## Algebraic Proof of the Existence of only 5 Platonic Solids

FoldUnfold Table of Contents Algebraic Proof of the Existence of only 5 Platonic Solids Algebraic Proof of the Existence of only 5 Platonic Solids We have already seen an intuitive proof for this, but now let's apply some of our recent results from planar graphs to prove that there are only $5$ platonic solids. Theorem 1: There are only $5$ platonic solids. Proof: We break … [Read more...]

## Conditions for Planarity

FoldUnfold Table of Contents Conditions for Planarity Conditions for Planarity We are now going to look at some conditions to determine if a graph is planar or not. Lemma 1: Let $G$ be a simple connected planar graph on $v$ vertices where $v \geq 3$ and $e$ edges. If the length of the shorted cycle in $G$ is $3$ (and hence the graph contains triangles), then $e \leq 3v - … [Read more...]

## The 5 Platonic Solids

FoldUnfold Table of Contents The 5 Platonic Solids The 5 Platonic Solids On earlier pages such as when we were looking at graphs of platonic solids, we made note of the five platonic solids, the tetrahedron, icosahedron, dodecahedron, octahedron, and cube, as well as their properties: Platonic Solid Number of Vertices Number of Faces Number of Edges $v + f - … [Read more...]

## Planar Graphs and Plane Drawings

FoldUnfold Table of Contents Planar Graphs and Plane Drawings The Degree of a Face The Handshaking Lemma for Planar Graphs Planar Graphs and Plane Drawings Definition: A graph is considered Planar if it can be redrawn such that no edges intersect. That is, a graph is planar if there exists a plane drawing of the graph. In many instances, we may want to see if a graph can be … [Read more...]

## Polygons and Polyhedra

FoldUnfold Table of Contents Polygons and Polyhedra Euler's Formula Polygons and Polyhedra Before we continue on with Euler's Formula, we're going to first look at some important definitions in geometry that will be used quite often on this page: Definition: A Polygon is a closed plane figure consisting of three edges at minimum, with each of these edges being straight. … [Read more...]

## Relation of Min Vertex Cutsets, Min Edge Cutsets, The Minimum Degree, and Maximum Degree

FoldUnfold Table of Contents Relation of Min Vertex Cutsets, Min Edge Cutsets, The Minimum Degree, and Maximum Degree Relation of Min Vertex Cutsets, Min Edge Cutsets, The Minimum Degree, and Maximum Degree We are going to prove the following inequality relating the minimum vertex cutset $\kappa (G)$, the minimum edge cutset $\lambda (G)$, the minimum degree in a graph … [Read more...]

## Vertex Cutsets

FoldUnfold Table of Contents Vertex Cutsets Vertex Connectivity Edge Cutsets Edge Connectivity Defining how connected a graph is, is sometimes difficult. We will now define connectivity of a graph in terms of what are called vertex cutsets and edge cutsets. Vertex Cutsets Definition: For a connected graph $G = (V(G), E(G))$, a Vertex Cutset is a subset $W$ of the vertex set … [Read more...]

## Fleury’s Algorithm

FoldUnfold Table of Contents Fleury's Algorithm Steps to Fleury's Algorithm Fleury's Algorithm Fleury's algorithm is very important in allowing us to be able to construct an Eulerian trail given an Eulerian graph $G$. We briefly describe this algorithm below. Steps to Fleury's Algorithm Step 1 Select any vertex to start with. Step 2 Traverse any available edge starting with … [Read more...]