A little graph theory

Basically, some graphs are the same. Basically.

Like these two:

Screenshot 2018-03-12 at 8.24.45 PM

And if you don’t believe me, pretend that you tangled the right graph. You end up with something basically identical to the left one.

Screenshot 2018-03-12 at 8.25.18 PM

Straighten out both of these, and you get just a straight line, or a chain. That’s another way of seeing that they’re both (basically) the same:

Screenshot 2018-03-12 at 9.00.08 PM

Here is another pair of graphs. They’re also basically the same, i.e. isomorphic!

Screenshot 2018-03-12 at 8.25.34 PM

I like imagining swinging around the parts of these graphs to convince myself that they really are the same.

Screenshot 2018-03-12 at 8.28.10 PM

I took the above examples from the truly fantastic Introduction to Graph Theory by Richard Trudeau. I found it lying around the math department office and have been carrying it around since. (Though I get why they changed it, the original title was “Dots and Lines” which is awesome.)

Here are a few more of Trudeau’s puzzles. In each pair, are the graphs isomorphic (i.e. basically the same)?

Screenshot 2018-03-12 at 8.28.59 PM.png

Screenshot 2018-03-12 at 8.28.26 PM.png

Screenshot 2018-03-12 at 8.28.44 PM.png

You can check yourself by playing with the diagrams digitally, trying to drag the points around to change their appearances. Here are links to all of the diagram pairs I’ve so far shared:

https://www.desmos.com/geometry/wjpe5onict

https://www.desmos.com/geometry/2es7o8rydj

https://www.desmos.com/geometry/fbd4wdcrbd

https://www.desmos.com/geometry/cflcmpkazm

https://www.desmos.com/geometry/vv0awlot9b

***

I love the idea of opposites in math, and there is a great way to think about what the opposite of a graph should be. The fancy term is “complement” but I like thinking of every graph as having an “anti-graph.” Here are some examples:

Screenshot 2018-03-12 at 9.54.10 PM

If you overlay the graph and its anti-graph, the result should be a completely connected graph. Meaning, a graph’s complement should consist of just the edges that are missing from the original.

Now, here is an AWESOME question: are any graphs the same as their anti-graphs? Are any graphs their own opposites? One last way of putting the question, to maximize googleability: are any graphs self-complementary?

The answer is, definitely! Mess around with the graphs in the image above to see what I mean:

https://www.desmos.com/geometry/bl7sc2yyul

One way to start looking for self-complementary graphs is by thinking about the number of edges that a graph with n dots can have, if it is going to be (basically) the same as its anti-graph. After all, the complement can’t have more edges than the original graph…

And then it’s fun to think about how many vertices (dots) a graph can have if it’s going to evenly split its edges between the graph and its complement. For instance, if you have 6 vertices there is a maximum of 15 edges — so there’s no way any graph with 6 vertices could be self-complementary, because there’s no way for a graph and its complement to have an equal share of 15 edges.

It’s fun to look for both of the 5-vertex graphs that are self-complementary.

It’s fun to ask how many graphs that look like empty rings (i.e. a regular polygon) are self-complementary. There’s at least one…

And those are all the fun things that I know about self-complementary graphs. I know it’s not a ton, but nearly all of it can be shared with young children.

Advertisements

2 thoughts on “A little graph theory

  1. Hi there. Thanks for sharing this – I didn’t know you were able to do this on Desmos. Your post says that each pair of graphs are isomorphic, however the first and third graphs are examples of graphs that are not isomorphic. Trudeau uses these examples to demonstrate graphs that are not isomorphic by checking the degree of each vertex.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s