8.03 Types of networks

We call a network on n vertices complete if every vertex is connected to every other vertex. There is exactly one complete network for each value of n.

The degree of each individual vertex is equal to one less than the number of vertices overall. In other words, if you take n vertices and connect one to all the others, you draw n-1 edges from each vertex.

If we take a network and delete some edges, or some of its vertices (and all edges connected to it), we obtain a subnetwork of the original. We often say that one network is a subnetwork of another network if we can get from one to the other through these deletions.

For example, any simple network that has n vertices is a subnetwork of the complete network with n vertices - we can just add or delete edges to get from one to the other:

The network on the left has the red edges added in, and then the vertices moved a little. We end up with a complete network. We can then go backwards - start at the right, delete the red edges, and move the vertices a little to recover the original network.

For an undirected network, we call it connected if we can move from any vertex to any other vertex, and disconnected if we can’t. We use the same words for a directed network, though we allow ourselves to move along the (directed) edges in both directions.

The top two networks are connected, the bottom two are disconnected.

These ideas comes up frequently in chemistry, as chemicals are frequently represented as a network. Here are three examples:

The degree of the vertex corresponds to the element. Hydrogen (orange) always has degree 1, oxygen (blue) degree 2, nitrogen (purple) degree 3,and carbon (green) degree 4.

These three chemicals have a common subnetwork - the “benzene ring” of six carbon atoms, with some hydrogens still attached.

Each of the three chemical’s networks have a single edge connecting this network to the top part, called the "functional group". Nature, and human chemistry, routinely takes a functional group from a molecule and replaces it with another by deleting and then restoring the edge - you can investigate these biochemical pathways (represented as a network) further here.

We can create subnetworks by eliminating a single edge. If the resulting subnetwork is disconnected, then we give that edge a special name - a bridge. These edges often represent critical connections in a network, because without them the network is broken into two pieces.

The three edges highlighted in orange are bridges, since deleting them would result in a disconnected network. The other edges could each be deleted and the network would still stay as one piece.

You may have noticed that networks often have their edges crossing over each other. But maybe there’s a way to move the vertices into a certain configuration so that none of the edges cross each other anymore. Such a configuration is called a planar representation, and networks that have one are called planar networks.

It isn’t always obvious at first glance whether a network is planar or non-planar - sometimes you have to move the vertices around for a long time before none of the edges cross each other anymore.

The top graph is planar, and below it are three of its equivalent planar representations.

Once a planar network is maneuvered into a planar representation, we can define a face (or region) as the area of the plane bounded by edges. The part of the plane outside the network is also a face.

In all three planar representations of the network from earlier, each face has been given a different colour - this network has 4 faces.

The octahedral graph below (which represents a 3-dimensional octahedron solid) has 8 faces.

Non-simple networks that are planar also have faces, though some of their faces are bounded by only one or only two edges:

The network on the left has 6 faces, with 4 of them bounded by only 1 edge (loops). The network on the right has 5 faces, with 2 of them bounded by only 2 edges.

However, if a network is not planar, then there are no faces to define - the crossing of edges makes it impossible.

The Swiss mathematician Leonhard Euler (pronounced “OIL-er”) was a pioneer in the mathematics of networks in the 18th century. He noticed something interesting about networks that are connected and planar, which is that the number of vertices v, the number of edges e, and the number of faces f, satisfy the formula:v+f-e=2

We call this formula Euler's formula.

This is a planar network.

It has 6 vertices, 9 edges, and 5 faces,applying Euler's we obtain:6+5-9=2

Let’s try again with the octahedral network:

Euler’s formula only works with planar networks, and this doesn’t look planar - the edges cross each other. But even though this is not a planar representation, we can check if there is one by checking if the formula it true.

6 +8 - 12 = 2

It is true so this is a planar network we would now need to find the planar representation.

Examples

Example 1

Consider the graph shown below.

a

Match the graph with its equivalent planar representation.

A

B

C

D

Worked Solution

Create a strategy

Redraw the edges that are crossing each other on the given graph. Make sure that the vertices that were connected by an edge on the original graph are still connected on the planar graph.

Apply the idea

All the graphs among the options do not contain any intersecting edges. So they are all planar graphs.

Only the graph in option A has the same edges, HD and BF, as in the original graph.

So the correct answer is option A.

Watch question walkthrough

b

How many regions does this representation have?

Worked Solution

Create a strategy

Use the Euler's formula for a connected planar graph given by:v+f-e=2 where v is the number of vertices, f is the number of faces, and e is the number of edges.

Apply the idea

We are given v=8 and e=10.

\displaystyle v+f-e	\displaystyle =	\displaystyle 2	Write the formula
\displaystyle 8+f-10	\displaystyle =	\displaystyle 2	Substitute v and e
\displaystyle -2 + f	\displaystyle =	\displaystyle 2	Evaluate
\displaystyle f	\displaystyle =	\displaystyle 4	Add 2 to both sides

Watch question walkthrough

Example 2

A connected planar graph has 11 edges, and 5 vertices. Solve for R, the number of regions.

Worked Solution

Create a strategy

Use the Euler's formula: V+R-E=2 where V is the number of vertices, R is the number of regions, and E is the number of edges.

Apply the idea

\displaystyle V+R-E	\displaystyle =	\displaystyle 2	Write the formula
\displaystyle 5+R-11	\displaystyle =	\displaystyle 2	Substitute V=5 and E=11
\displaystyle R-6	\displaystyle =	\displaystyle 2	Subtract like terms
\displaystyle R	\displaystyle =	\displaystyle 8	Add 6 to both sides

Watch question walkthrough