Question 2

Today, we will explore a simple graph with 6 vertices. Can anyone explain what we mean by a 'simple graph'?

A simple graph has no loops or multiple edges between the same pair of vertices.

Correct! The graph consists only of edges connecting distinct vertices. Now, what happens when we delete a vertex?

The edges connected to that vertex are also removed.

Exactly! This is a key concept we'll use. Deleting a vertex decreases the total edge count based on that vertex's degree. Remember this phrase: 'Deleting a vertex, reduces the edges pertaining to its degree'.

Now, let's discuss specific vertex deletion. If I delete vertex v1, I end up with 7 edges remaining. What does this imply?

It means that the degree of vertex v1 must have been 1, because 8 total edges minus 1 is 7.

Great observation! The relationship here is that the original edge count decreases by the vertex degree. Each vertex deletion gives us an equation to work with. Let's write this down!

So we can keep track of the degree of each vertex like this?

Precisely! Keep a log of the degrees as we formulate our equations.

Let's summarize the equations we've formed from our vertex deletions. We derived that each deletion correlates to a specific degree.

And we can add all those equations together to obtain a single equation?

Exactly! By summing all results, we derive a larger equation involving the total edge count, which is our goal.

What happens next once we have that big equation?

From there, we apply the handshaking theorem to relate the sum of degrees to the cardinality of edges, allowing us to solve for the original edge count.