Graph Terminology and Key Concepts | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 9.2 Free with a free account

Graph Terminology and Key Concepts

Discrete Mathematics · Chapter 9: Graph Theory: Foundations and Euler PathsSection 9.2 · lesson 60 of 879 min · free with a free account

← Graphs: Vertices, Edges, and Basic DefinitionsNext lesson: Types of Graphs and Their Properties →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Degree, ways of moving through a graph, and being in 1 piece.

  • Compute degrees and a degree sequence
  • Prove and use the Handshaking Lemma
  • Tell walks, trails, paths, circuits and cycles apart
  • Find the connected components of a graph

Transcript

Everything said in the video, section by section (1,252 words). Read along, or search it.

Graph Theory: Foundations and Euler Paths

Graph Terminology and Key Concepts

Section nine point one defined what a graph is. This section gives the precise language for how a graph is put together, and how one moves through it. We'll cover degree and the handshaking lemma, the five ways of moving through a graph, and what it means for a graph to be in one piece.

The Opening Problem

4,000 Requests in a Day

A social platform's abuse detection team notices something odd. One account has sent friend requests to four thousand people in a single day, while a typical account averages fewer than ten new connections a week. Flagging that account doesn't need the platform's entire network structure. It needs one number. How many edges touch that vertex. That's its degree. The same network raises a second question. If two accounts connect only through a long, winding chain of mutual friends, is it still one connected community? Or has it quietly split into isolated clusters, as happens when a user base fragments across regions with no cross-region friendships?

Definition 9.2.1 and Theorem 9.2.1

Degree, and the Handshaking Lemma

The degree of a vertex v is the number of edges incident to it, the number of edges with v as an endpoint. A loop would count twice. The handshaking lemma says that in any undirected graph, the degrees add up to exactly twice the number of edges. Here's why. Adding up the degrees counts, for every vertex, the edges touching it. That's the same as counting, for every edge, its endpoints. And each edge has exactly two. So the sum is even. Split it into even-degree and odd-degree vertices. The even ones contribute an even total, so the odd ones must too. And a sum of odd numbers is even only when there's an even count of them. So the number of odd-degree vertices is always even.

Worked Example 9.2.1

A Sensor Network's Degree Sequence

Here's a small network of five roadside sensor units, where an edge means two units can communicate directly. Tally the edges at each vertex. A has three, B has two, C has three, D has three, and E has just one. The degree sequence, the list of degrees from largest to smallest, is three, three, three, two, one. They add to twelve. There are six edges, and twice six is twelve, so the tally checks out. And there are four odd-degree vertices, an even count, just as the lemma predicts. A degree sequence is a useful fingerprint. Graphs with different sequences can't be structurally identical. But matching sequences don't guarantee the graphs are the same.

Definitions 9.2.2 to 9.2.4

Walk, Trail, Path

Several related terms describe moving through a graph. They differ precisely in which repetitions are allowed. A walk is an alternating sequence of vertices and edges, where each edge joins the vertices on either side. Its length is the number of edges. Anything may repeat. A trail is a walk with no repeated edge. Vertices may still repeat. A path is a trail with no repeated vertex. Since no vertex repeats, no edge can either. Mixing these terms up is one of the most common sources of error when analyzing graph algorithms.

Definitions 9.2.5 and 9.2.6

Circuits and Cycles

Two more terms add a closure condition. A circuit is a trail that starts and ends at the same vertex, with length at least one. Interior vertices may repeat. Only repeated edges are forbidden. A cycle is a circuit whose only repeated vertex is the shared start and end. In a simple graph, it has length at least three. The containments are strict. Every path is a trail, and every trail is a walk. Every cycle is a circuit, and every circuit is a trail.

Table 1

5 Terms, 3 Conditions

This table compares the five terms along three conditions. A walk allows repeated vertices and repeated edges, and needn't be closed. A trail forbids repeated edges. A path forbids repeated vertices too, so its endpoints are distinct. A circuit is a closed trail, which may revisit interior vertices. And a cycle is a closed trail, where only the shared endpoint repeats. Reading down a column shows the restrictions accumulating as the terms get more specific.

Worked Example 9.2.2

Classifying 3 Delivery Routes

Now classify three routes through five delivery checkpoints, P, Q, R, S, and T. The edges form a loop around the five, plus a shortcut from Q to T. First, P, Q, T, P, and back to Q. Every step follows an edge, so it's a walk. But the edge from P to Q is used twice, so it isn't a trail. That rules out path, circuit, and cycle too. It's a walk only. Second, P, Q, R, S, T. All four edges are distinct, and so are all five vertices. So it's a trail and a path. But it doesn't return to P, so it's neither a circuit nor a cycle. Third, P, Q, R, S, T, and back to P. All five edges are distinct, and it returns to its start. So it's a circuit. The only repeated vertex is the shared endpoint P, and its length, five, is at least three. So it's also a cycle.

Figure 2

The Cycle P, Q, R, S, T, P

Here's that third route in the graph. The highlighted edges trace P, Q, R, S, T, and back to P. The dashed shortcut from Q to T isn't used. It returns to P, uses five distinct edges, and repeats no interior vertex. That makes it a cycle. By convention, it isn't a path. A path has distinct endpoints. Closed routes like this are captured separately, as circuits and cycles.

Definitions 9.2.7 and 9.2.8

Connected, and Components

This vocabulary makes it possible to say precisely, what it means for a graph to be in one piece. A graph is connected if every pair of vertices is joined by a walk. Equivalently, by a path, since repeated portions of a walk can always be cut out. A connected component is a maximal connected piece. Every pair of its vertices is joined, and no vertex outside can reach it. Every vertex belongs to exactly one component. And a graph is connected exactly when it has one component. That's a practical question. A network provider checking its router backbone after a fiber cut is asking exactly this. If it's split into two components, some routers can't reach others at all, however long the path.

Worked Example 9.2.3

3 Clusters of Researchers

Here's a collaboration graph of eight research accounts. The edges are one-two, two-three, one-three, four-five, five-six, and seven-eight. Start at one. It reaches two, and two reaches three, but nothing from those three reaches outside. So one, two, three is a component. Move to an unvisited vertex, four. It reaches five, and five reaches six. That's a second component. Then seven reaches only eight. A third. Every vertex is now assigned, so there are three components. The graph isn't connected. The collaboration network has fragmented into three clusters that can't reach each other. The code automates exactly that search, using breadth-first search from each unvisited vertex. That technique is developed fully in section nine point four.

Takeaways

Measure, Move, Connect

To summarize. The degree of a vertex counts its incident edges. The handshaking lemma says the degrees add to twice the number of edges, so the total is always even. Walk, trail, and path form a nested hierarchy. A trail forbids repeated edges, and a path forbids repeated vertices. Circuit and cycle add closure. And a graph is connected exactly when it has one component. Here's something to think about. A network engineer wants to know whether a set of cable connections contains a wasteful loop, one that could be removed without disconnecting anything. Would an algorithm that detects circuits, and one that detects cycles, flag the same graphs? Can a graph contain a circuit without containing any cycle? What would the smallest possible example need to look like?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Graph Terminology and Key Concepts

What is the degree of a vertex, and how do you find a degree sequence?
The degree of a vertex is the number of edges incident to it, with a loop counting twice. The degree sequence lists all the degrees from largest to smallest. A five-vertex sensor network with degrees 3, 2, 3, 3, 1 has degree sequence 3, 3, 3, 2, 1. Different sequences mean the graphs are not structurally identical, but matching sequences do not guarantee the graphs are the same.
What is the Handshaking Lemma and why is the number of odd-degree vertices always even?
The Handshaking Lemma says that in an undirected graph the degrees add up to exactly twice the number of edges, \sum_v \deg(v) = 2|E|. Summing degrees counts each edge once at each of its two endpoints, so the total is even. The even-degree vertices contribute an even amount, so the odd-degree vertices must also sum to an even number. That forces an even count of them.
What is the difference between a walk, trail, path, circuit, and cycle?
The five terms differ in which repetitions they allow. A walk is an alternating sequence of vertices and edges where anything may repeat. A trail is a walk with no repeated edge, and a path is a trail with no repeated vertex. A circuit is a closed trail, and a cycle is a circuit whose only repeated vertex is the shared start and end. Every path is a trail, and every trail is a walk.
How do you find the connected components of a graph?
Start at any vertex, collect everything reachable from it to form one component, then repeat from a vertex not yet visited until every vertex is assigned. For edges 1-2, 2-3, 1-3, 4-5, 5-6, and 7-8 on eight vertices, this gives the components {1, 2, 3}, {4, 5, 6}, and {7, 8}. A graph is connected exactly when it has one component.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →