Completely Connected Graphs (Part 1)

Here are some completely different problems that turn out to be basically the same math problem:

1. You are doing an ice breaker on the first day of class. If everyone introduces themselves to everyone else then how many unique conversations will happen for a class of 25 people? 50 people?

2. You are in a dance class where you have dance partners. The instructor says that it is important for everyone to try being dance partners with everyone else to get practice. How many unique sets of dance parners are there for 30 dancers?

3. There is a group of tiny spacecraft exploring deep space. Each spacecraft can send a unique signal back to home base so it is easy to count the total number of spacecraft. What is much harder is figuring out if all the spacecraft can communicate with each other. The space craft are configured so that once a day they all try to communicate with as many other spacecraft as they can. When they make a connection to a spacecraft they have not communicated with yet that day they each send a special signal back to the base. For a fleet of 30 spacecraft, how many of these signals would you expect to receive if all the craft are communicating with each other?

4. There are 16 chemicals that are needed to manufacture a new product that is being designed at your company. If any two of these chemicals react with each other then bad things happen and the whole product needs to be redesigned. It takes 3 hours to run tests to see if two chemicals will react with each other. Your boss wants you to figure out how long it will take to run all the needed tests.

5. Your school is getting rid of 20 laptops and you want to connect them all together to make a supercomputer. If each laptop has a direct ethernet connection to every other laptop, how many ethernet cables are you going to need?

You might think that to answer each of these questions we should look in a dance textbook, or an aerospace engineering textbook or a chemistry textbook or a computer science textbook. It turns out, from a mathematical perspective, these are all the same problem!

In a math textbook, these problems are called "completely connected graphs". Here is an example of a completely connected graph with four things (dancers, spacecraft, chemicals, laptops, etc.)

It is not too hard to look at the diagram above and see that with four things there are six different pairs. In other words there are six different unique connections between the four things.

With four things it is pretty easy to just count the number of unique connections. Likewise, with five things it is not too hard to draw it out and count the connections. But what are you going to do when there are 30 things? Or 300? Or more? Eventually we will make a computer program to do the counting for us!

Step 0. Come up with a scenario!

The introduction to this activity mentions five completely different situations where understanding the number of combinations or pairs would be important. Come up with another scenario (hopefully one that is interesting to you) where something like this would come up. Use your imagination! How could these ideas be relevant to sports? politics? social media? etc.

Step 1. Open up a simple code

Click here to open up a simple code

Go ahead and press in the top left to run the code. The output it produces will look like this:

There are four vertices in this graph but only two of them are connected.

Notice: The program will automatically count the number of vertices (i.e. the circles) and the number of edges (i.e. the lines).

This is a very nice feature because all you need to do is add drawEdges commands to draw lines between all the nodes and the program will tell you how many lines you have drawn.

If the program can detect that something is wrong with your code it will show a red next to that objective.

If the program can detect that you have completed the objective it will show a green check mark next to that objective.

But the program is not very smart. If it can't tell whether you have completed the objective it will indicate a question mark like this next to that objective.

By the end of this activity your goal is to have green check marks next to all the objectives like this:

The directions below will help you meet all these objectives.

Step 2. Look at the code

Here is what the code looks like:

//showaxes = true;

function draw(){

  // clear the screen and other stuff
  display();

  drawVertices(100,100); // x,y
  drawVertices(300,300);
  drawVertices(300,100);
  drawVertices(100,300);
  drawEdges(100,300,300,300); // x1,y1,x2,y2
  
} // end draw() DO NOT ADD ANY CODE AFTER THIS LINE!!!

As you can see there are four drawVertices commands that draw circles on the screen and one drawEdges command that draws a line on the screen. Not coincidentally, there is a message at the bottom left part of the screen that says:

Number of vertices = 4;

Number of edges = 1;

Step 3. Show the axes

At the beginning of the program there is a line of code:

//showaxes = true;

To see the coordinate axes go ahead and REMOVE the //

showaxes = true;

If you make this change your code will behave like this

Step 4. Remove drawVertices(300,300);

One of the drawVertices commands is this one:

  drawVertices(300,300);

The big question is whether this is the circle to the top left, top right, bottom left or bottom right. What do you think? Make a guess!

To figure out which circle it is, comment out this line of code like this:

  // drawVertices(300,300);

Now run the program. Which circle is missing?

Step 5. Add edges

Step 5a. Undo Step 4

Remove the // in front of drawVertices(300,300); so that all four vertices appear on screen.

Step 5b. Add edges until completely connected

The code currently has one connection:

  drawEdges(100,300,300,300); // x1,y1,x2,y2

As suggested by the comment, this is a line between the point (x₁, y₁) and the point (x₂,y₂).

Add more drawEdges commands to your code until every vertex is connected to every other vertex like in this image:

With four vertices, how many unique connections are there?

Count the vertices and compare to the number written below the sketch. Are they the same?

Step 6. Consider six vertices (Hexagon-like completely connected graph)

Add two more vertices to your graph:

  drawVertices(50,200);
  drawVertices(350,200);

At this point your graph will look like this image:

Now add connections to the graph so that the new vertices connect with all the other vertices and with each other.

When you are finished your graph should look like this image:

At this point you should have all green check marks! Yay!

How many edges are there for a completely connected graph with six vertices?

Step 7. Fill in a table of Vertices versus Edges

It is getting hard to keep track of how many edges there are for a particular number of vertices. Here is a table we can use:

  drawVertices(200,50);
  drawVertices(200,350);