In this lesson, we define connected graphs and complete graphs. Then we analyze the similarities and differences between these two types of graphs and use them to complete an example involving graphs.
Overview of Graphs
Suppose a contractor, Shelly, is creating a neighborhood of six houses that are arranged in such a way that they enclose a forested area. Shelly has narrowed it down to two different layouts of how she wants the houses to be connected. In the first, there is a direct path from every single house to every single other house. In the second, there is a way to get from each of the houses to each of the other houses, but it’s not necessarily a direct path.
In the branch of mathematics called graph theory, both of these layouts are examples of graphs, where a graph is a collection points called vertices, and line segments between those vertices are called edges. We call the number of edges that a vertex contains the degree of the vertex. In the case of the layouts, the houses are vertices, and the direct paths between them are edges.
Types of Graphs
In graph theory, there are different types of graphs, and the two layouts of houses each represent a different type of graph. The first is an example of a complete graph. In a complete graph, there is an edge between every single pair of vertices in the graph. The second is an example of a connected graph. In a connected graph, it’s possible to get from every vertex in the graph to every other vertex in the graph through a series of edges, called a path.
Notice that by the definition of a connected graph, we can reach every vertex from every other vertex. Since there is an edge between every pair of vertices in a complete graph, it must be the case that every complete graph is a connected graph. However, since it’s not necessarily the case that there is an edge between every vertex in a connected graph, not all connected graphs are complete graphs.
Because of this, connected graphs and complete graphs have similarities and differences. Let’s consider some of the simpler similarities and differences of these two types of graphs.
We will start with some similarities.
In both types of graphs, it’s possible to get from every vertex to every other vertex through a series of edges.
All vertices in both graphs have a degree of at least 1.
Both types of graphs are made up of exactly one part.
Now, let’s look at some differences between these two types of graphs.
All complete graphs are connected graphs, but not all connected graphs are complete graphs.
It only takes one edge to get from any vertex to any other vertex in a complete graph. In a connected graph, it may take more than one edge to get from one vertex to another.
If a complete graph has n > 1 vertices, then each vertex has degree n – 1. In a connected graph with n vertices, a vertex may have any degree greater than or equal to 1.
After seeing some of these similarities and differences, why don’t we use these and the definitions of each of these types of graphs to do some examples?
Consider this graph:
First of all, we want to determine if the graph is complete, connected, both, or neither. Well, notice that there are two parts that make up this graph, and we saw in the similarities between the two types of graphs that both a complete graph and a connected graph have only one part, so this graph is neither complete nor connected.