Graph Theory Concepts and Terminology

An error occurred trying to load this video.

Try refreshing the page, or contact customer support.

Coming up next: Euler Paths and Euler's Circuits

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:01 A Graph
  • 1:35 Vertices
  • 3:36 Edges
  • 4:05 Paths and Others
  • 6:26 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
Lesson Transcript
Instructor: Yuanxin (Amy) Yang Alcocer

Amy has a master's degree in secondary education and has taught math at a public charter high school.

After watching this video lesson, you will better understand the workings of a graph in graph theory. Learn the key terms that you will see and what they look like on the graph. Also, learn how to navigate a graph.

A Graph

The graphs that you see in graph theory, the study of graphs, look a lot like a connect the dots game. However, you won't always get a nice picture at the end. You will instead get a lot of dots with various lines connecting the dots. And, unlike the connect the dots game, some of the points may have more than one line connecting it to others. The graphs will look something like this:

graph concepts

This is an example of a simple graph. It looks like a connect the dots game, doesn't it? But the finished product doesn't look like a cute animal or an interesting object. It just looks like a bunch of dots with lines connecting them together. The study of how these lines connect the dots is what graph theory is all about.

It may sound boring and pointless, but if you think about a city, its many intersections and roads, and then you think about planning the best route to get from point A to point B, then you might see how graph theory comes into play. Graph theory allows you to find the best route given the roads that connect the various intersections. Look at the graph again, and you might be able to see a little village now. The circles are houses, and the lines are roads connecting the houses. This is just one application of graph theory, and there are others. But it shows how important graph theory is. That is why there is a whole field of math devoted to this study.

Vertices

As you delve deeper into graph theory, you will come across a few very important key terms, which we will cover in this video lesson. We begin with the terms related to our vertices, our points.

We can have several different styles of vertices. We can have an isolated vertex, which is a vertex with no lines connecting it to others. An isolated vertex in a graph will be all by itself. It won't have any connections.

graph concepts

The vertex to the far right in this graph is an isolated vertex. See how it has no lines connecting it to others? It looks rather lonely. If our graph represents a little village, then this isolated vertex might be a house with no roads to it. You'd have to walk through wilderness to get to it.

Another term that you are likely to see is adjacent vertices. This refers to connected vertices that are next to each other. For example, looking at our last graph, the two vertices at the very top of our graph are adjacent vertices because they are connected, and they are next to each other.

Next, we have the degree of a vertex. This tells us how many lines are connected to the vertex. For example, the isolated vertex has a degree of 0. The vertex to the very far left has a degree of 2 because it has two lines. The vertex at the very top has a degree of 3 because it has three lines connecting it to others. If our degree is even, we call the vertex an even vertex. If the degree is odd, then we call it an odd vertex. That's pretty easy to remember. Odd for an odd number of connections and even for an even number of connections.

Edges

Now, let's go over the terms for edges, our lines. We can have multiples edges if we have roads that are parallel to each other or lines that connect the same vertices together. We also have adjacent edges, which, like an adjacent vertex, are edges that are next to each other. Looking at our graph, the edges at the far left of the graph are adjacent because they are next to each other.

Paths and Others

Now that we've covered the terms for vertices and edges, let's talk about the terms for other aspects of our graph. Here, we have what is called a path, a route taking you from one vertex to another. For example, we may want to get from the house at the far left, point A, to the house at the way bottom, point B.

graph concepts

The edges that we take and the vertices that we pass through are all part of our path. The number of edges that we take is referred to as the length of the path. So, for example, if we started going down from point A and continued taking the lowest edges, we would have a path length of 3 since we used three edges to get from point A to point B. If our path takes us from one point, say point A, and it takes us back to the same point A, then we call this path a circuit.

graph concepts

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