Graphs: Vertices, Edges, and Basic Definitions | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Graphs: Vertices, Edges, and Basic Definitions

Discrete Mathematics · Chapter 9: Graph Theory: Foundations and Euler PathsSection 9.1 · lesson 59 of 8710 min · free with a free account

← The Inclusion-Exclusion PrincipleNext lesson: Graph Terminology and Key Concepts →

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

A set of things, and a set of connections between them.

  • Define a graph formally
  • Distinguish directed, undirected and simple graphs
  • Use adjacency and incidence
  • Store a graph as a matrix or a list

Transcript

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

Graph Theory: Foundations and Euler Paths

Graphs: Vertices, Edges, and Basic Definitions

Chapter nine begins graph theory. This first section defines what a graph is, precisely. We'll cover directed, undirected, and simple graphs, the relations of adjacency and incidence, and the two standard ways a program stores a graph.

The Opening Problem

The Same Structure, Everywhere

A campus I T office sketches which server racks are cabled directly to which others. A ride-hailing platform decides which intersections connect without passing through a third. A social platform decides whose posts appear in a feed, based on who follows whom. Each one relies, often without naming it, on one of the most flexible structures in discrete mathematics. The graph. Here, graph doesn't mean a bar chart or a scatterplot. It means an object built from exactly two ingredients. A set of things, and a set of connections between pairs of those things. That simplicity is what makes it powerful. The same structure describes wired servers, followers, web links, or airline routes. But before richer questions, like shortest routes or reachability, can even be asked, the structure has to be defined with complete precision.

Definition 9.1

A Graph Is a Pair of Sets

A graph is an ordered pair, G equals V comma E. V is a finite, nonempty set of vertices, also called nodes in computing. E is a set of edges, each an unordered pair of two distinct vertices. Those are the edge's endpoints. The number of vertices is called the order of the graph, and the number of edges is its size. Nothing is assumed about what the vertices are. They might be servers, people, cities, or web pages. And the definition says nothing about direction. The pair u, v is the same set as v, u. A cable linking two machines carries signals both ways, with no forward or backward version.

Worked Example 9.1

A Server-Room Network

Here's a small server room with five machines, S one through S five. A technician records which pairs are joined by a direct fiber cable. S one to S two, S one to S three, and S two to S three. Then S two to S four, S three to S four, and S four to S five. That translates straight into the definition. V is the five machines, and E is those six unordered pairs. So the order is five, and the size is six. Because each cable works in both directions, the unordered model fits exactly, with nothing lost. And a drawing of this graph carries only what's in V and E. The physical layout of the room, and the lengths of the cables, aren't part of the mathematical object.

Definition 9.2

When Direction Matters

Not every relationship is symmetric the way a cable is. On a social platform, if Ana follows Ben, nothing guarantees that Ben follows Ana. An edge model that can't tell those apart would lose real information. That motivates a second kind of graph, where edges have direction. A directed graph, or digraph, has edges that are ordered pairs, called arcs. The arc u comma v is drawn as an arrow from u, the tail, to v, the head. The whole difference is packaging. An undirected edge is a set, so its order never matters. A directed edge is an ordered pair, so u comma v and v comma u differ, unless u equals v. That means a digraph can contain one arc without the other. Or it can contain both, as two separate arcs.

Definition 9.3

Simple Graphs

Both definitions still allow two irregularities worth ruling out. One is a loop, an edge from a vertex to itself. The other is parallel edges, more than one edge between the same pair of vertices, in the same direction. A graph with neither is called simple. And unless stated otherwise, graph in this course means a simple graph. That's not just bookkeeping. A link between two router interfaces is either present or absent. A follow either holds or doesn't, once per ordered pair of accounts. A graph that allows repeated connections is a multigraph. It's useful for, say, two streets joining the same intersections. But it's outside this course.

Worked Example 9.2

Modeling Follows as a Digraph

Now model follows as a digraph. Four accounts, Ana, Ben, Cleo, and Diego. Ana follows Ben and Cleo. Ben follows Cleo. Cleo follows Ana. And Diego follows Ben. Each x follows y becomes the arc x comma y. On the right of the picture, notice Ana and Cleo. Ana follows Cleo, and separately, Cleo follows Ana. Those are two distinct arcs, running in opposite directions. The server network is on the left for contrast. Its edges have no direction at all. The follows graph is simple too. Nobody follows themselves, and each ordered pair of accounts has at most one arc.

Why Direction Matters

Don't Overstate the Blast Radius

An undirected model of the same data would have to merge Ana follows Ben into a single edge. That silently discards the fact that the relationship only runs one way. Direction also matters for reasoning about how a problem spreads. In network security, traffic is often permitted in only one direction. Worker machines might be allowed to request records from a database server, while the database can't initiate connections back to the workers. If an attacker compromises a worker, the digraph of permitted connections determines which machines can be reached next. Collapsing it into an undirected graph would overstate how far a single compromise could spread.

Definitions 9.4 and 9.5

Adjacency and Incidence

Once a graph is defined, the next questions are usually computational. Are two vertices connected? Which vertices does this one connect to directly? Two vertices joined by an edge are adjacent. They're called neighbors. In a digraph, u is adjacent to v when the arc u comma v exists. And that doesn't imply v is adjacent to u. An edge is incident to a vertex if that vertex is one of its endpoints. So adjacency relates two vertices, while incidence relates a vertex and an edge. In the server network, S two and S four are adjacent. The edge between them is incident to both. And S two is incident to three edges in total.

Worked Example 9.3

The Adjacency Matrix

To answer adjacency questions efficiently, a program usually stores a graph in one of two standard ways. The first is an adjacency matrix. List the vertices in order. Entry i, j is one if vertex i and vertex j are adjacent, and zero otherwise. Checking all twenty-five ordered pairs for the server network gives this matrix. For a simple undirected graph, the matrix is symmetric across its main diagonal. And every diagonal entry is zero, since loops aren't allowed. Row S four has three ones, at S two, S three, and S five. Those match its three edges.

Worked Example 9.3

The Adjacency List

The second way is an adjacency list. It stores the same information more compactly, as a list of neighbors for each vertex. The function starts every vertex with an empty list. For each edge, it adds each endpoint to the other's list, since the graph is undirected. Running it on the server network gives S one, with neighbors S two and S three, down to S five, whose only neighbor is S four. Each line is exactly a row of the matrix. The two representations encode the same graph.

Table 9.1

Matrix or List?

The two representations trade off differently. A matrix needs space for every pair of vertices, however few edges there are. A list grows only with the number of vertices plus edges. Checking whether two vertices are adjacent takes one lookup in a matrix. In a list, it may mean scanning a vertex's neighbors. But listing all the neighbors of a vertex means reading a whole matrix row, versus just the actual neighbors in a list. Real computing networks, like web links, social graphs, and road networks, are sparse. Their edge counts are much closer to the number of vertices than to its square. That's why adjacency lists are the default in most production graph software.

Takeaways

2 Sets, and How to Store Them

To summarize. A graph is fully specified by a vertex set and an edge set. Labels and drawing layout aren't part of it. Undirected edges suit symmetric connections, like cables or mutual friendships. Directed edges suit one-way connections, like follows or permitted network calls. A simple graph has no loops and no parallel edges. Adjacency relates two vertices, and incidence relates a vertex and an edge. Here's something to think about. A platform models friendship as an undirected graph, since both people must accept. Later it adds close friends, which a user can assign to any friend without their approval. Can that be a label on the existing edges? Or does it need a fundamentally different structure? What does your answer reveal about the difference between a property of an edge, and an ordered relationship between two vertices?

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 Graphs: Vertices, Edges, and Basic Definitions

What is the formal definition of a graph in discrete math?
A graph is an ordered pair G = (V, E), where V is a finite, nonempty set of vertices and E is a set of edges, each an unordered pair of two distinct vertices. The number of vertices is the order and the number of edges is the size. A network of 5 machines joined by 6 cables has order 5 and size 6.
What is the difference between a directed graph, an undirected graph, and a simple graph?
An undirected graph has edges that are unordered pairs, so \{u,v\} and \{v,u\} are the same edge. A directed graph has arcs that are ordered pairs, so (u,v) differs from (v,u) when u \neq v. A simple graph has no loops and no parallel edges. In this course, "graph" means a simple graph unless stated otherwise.
What is the difference between adjacent and incident in graph theory?
Adjacency relates two vertices, while incidence relates a vertex and an edge. Two vertices are adjacent when an edge joins them. An edge is incident to a vertex if that vertex is one of its endpoints. In a digraph, u is adjacent to v when arc (u,v) exists, and that does not imply v is adjacent to u.
Should I store a graph as an adjacency matrix or an adjacency list?
Use a matrix when you need fast adjacency checks, and a list when the graph is sparse. An adjacency matrix has entry (i,j)=1 if vertices i and j are adjacent and 0 otherwise, but it uses space for every pair of vertices. A list stores only each vertex's neighbors, so its size grows with vertices plus edges. For a simple undirected graph, the matrix is symmetric with zeros on the diagonal.

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 →