My first ever exposure to any sort of graph theory was through this paper by Flapan, Mattman, Mellor, Naimi, and Nukkuni. If you’ve already clicked on the link, you might see how someone could get overwhelmed with terminology early on in the paper. Since I had no prior knowledge to graph theory, that person was me. The goal of this post is to provide some casual definitions and some examples showing off certain properties. (Note: this will not cover all definitions in the paper, and certainly not all definitions in graph theory, just some ones that I wish I knew before reading the paper/some ones I think need extra attention.)

[Note: all images are either from the paper linked above, or are from the wikipedia article linked in the definition title preceding the image.]

Definitions and Examples

Planar Graph: A graph is planar if it can be drawn on the plane without any of its edges crossing. (Note: only one way of drawing the graph without the edges crossing has to exist for it to be planar.)

K_n: This is a complete graph with n vertices. It will also have n(n-1)/2 edges. Below is a picture showing off K_n for n=1…12 along with the number of edges the graph has._for 

Minor: Let G be a graph and H be a subgraph. A minor of a graph is created by deleting edges and vertices, and contracting zero or more edges. (Note: when you contract an edge, the two vertices at the end of that edge merge.) Below is a diagram of a G: graph, H: minor of G, and how the minor was formed. The dotted line represents the deletion of an edge, while the grey line represents the contraction of an edge.

Y-Δ Transform/Move: Let G be a graph that has a vertex, v, and let v have exactly three other vertices surrounding it. A Y-Δ transform of G at v is achieved by removing v from G and adding edges between each pair of the neighboring vertices.

Δ-Y Transform/Move: Let H be a graph that has a triangle of vertices, uvw. A Δ-Y transform of H at uvw is achieved by removing the edges uv, vw, and uw from H and adding a new vertex, z,  and new edges uz, vz, and wz.

So, in Y-Δ transforms you are deleting a vertex and in Δ-Y transforms you are adding a vertex. These transforms will be useful for understanding an upcoming definition.

Petersen Graph: This is a graph with 10 vertices and 15 edges. Click on the link and scroll to read about some neat properties Petersen Graphs have. If I listed them all here, this definition would be the length of the blogpost.

Petersen Family of Graphs: This is a set of seven undirected graphs (graphs in which the edges don’t have direction) that includes the Petersen graph, the complete graph K₆  and 5 other graphs that are formed by Y-Δ and Δ-Y transforms. Below are two images: one from the paper mentioned at the beginning of this post and one from the Wikipedia page linked in this definition. Both show the Petersen family of graphs, but the Wikipedia picture shows which graphs can be formed by performing Y-Δ and Δ-Y transforms.

Upcoming

If you clicked on the paper mentioned at the beginning of the blog post, you may have noticed that the definitions featured here only cover the first three pages. These definitions and examples were chosen because they are going to be heavily used in what I want to do next. Past posts by Ben Flint have shown off Petersen graphs represented in 3-dimensions. My goal for the semester is to represent K₆ , K_3,3,1 , a Petersen graph, and the other 4 graphs in the Petersen family in 3-dimensions. A stretch goal/side project is to create some sort of program that will perform those Y-Δ and Δ-Y transforms on the Peterson family of graphs (and potentially others as well).

Until next time,

Hannah Critchfield