Connected Graph vs. Complete Graph Video

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Complete Graph: Definition & Example

You're on a roll. Keep up the good work!

Take Quiz Watch Next Lesson
 Replay
Your next lesson will play in 10 seconds
  • 0:04 Overview of Graphs
  • 0:53 Types of Graphs
  • 1:52 Similarities
  • 2:09 Differences
  • 2:50 Examples
  • 4:20 Lesson Summary
Save Save Save

Want to watch this again later?

Log in or sign up to add this lesson to a Custom Course.

Log in or Sign up

Timeline
Autoplay
Autoplay
Speed Speed

Recommended Lessons and Courses for You

Lesson Transcript
Instructor: Laura Pennington

Laura has taught collegiate mathematics and holds a master's degree in pure mathematics.

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.


compcon1


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.

Similarities

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.

Differences

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?

Examples

Consider this graph:


compconn2


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.

To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support