Types of Graphs and Their Properties | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

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

Types of Graphs and Their Properties

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

← Graph Terminology and Key ConceptsNext lesson: Graph Isomorphism and Homomorphism →

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

Complete, bipartite, regular, null - and multigraphs.

  • Count the edges of a complete graph
  • Test bipartiteness with the odd-cycle theorem
  • Recognize regular and null graphs
  • Model parallel connections with a multigraph

Transcript

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

Graph Theory: Foundations and Euler Paths

Types of Graphs and Their Properties

This section names the most important shapes a graph can take. Complete graphs, bipartite graphs, regular graphs, null graphs, and multigraphs. Each gets a precise definition, a property worth knowing, and a place in real network design.

The Opening Problem

Wiring a Data Center

A cloud infrastructure team is wiring the network for a new data center. Before a single cable is run, the topology is just a set of switches with no connections. Graph theory treats that as a legitimate graph, not an absence of one. Then the leaf switches, which connect to servers, are wired to the spine switches, which route traffic between leaves. Every leaf reaches every spine, and no leaf is wired to another leaf. Engineers call that leaf-spine. Mathematicians call it a complete bipartite graph. Within the spine layer, each switch has exactly the same number of neighbors, so none becomes a bottleneck. That's a regular graph. And between one leaf and one spine, the team may bundle two or three physical cables, for redundancy and bandwidth. A simple graph can't represent that. A multigraph can.

Definition 9.3.1 and Example 9.3.1

Complete Graphs

A complete graph on n vertices, written K n, is the simple graph where every pair of distinct vertices is joined by an edge. How many edges does it have? Each vertex is adjacent to the other n minus one, so every degree is n minus one. By the handshake lemma from section nine point two, the degrees add to twice the number of edges. So n times n minus one equals twice the edge count. That gives n times n minus one, over two, which is n choose two. It's the number of ways to pick an unordered pair of vertices, exactly matching the definition. Five fully meshed servers need ten direct links. But full mesh is rarely used at scale, because n choose two grows quadratically. Doubling the servers roughly quadruples the cables. That cost is what pushes designers toward leaf-spine instead.

Definition 9.3.2

Bipartite Graphs

A bipartite graph takes the opposite approach. The vertices split into two disjoint groups, and edges may only run between the groups, never within one. If every vertex in the first group is also adjacent to every vertex in the second, it's a complete bipartite graph, written K m comma n. Leaf-spine is exactly that. The first part is the leaf switches, the second is the spines, and every leaf is wired to every spine. The same structure appears in exam timetabling, with students on one side and exam slots on the other. And in recommendation systems, with users and products, where an edge records a purchase or a rating.

Theorem 9.3.1

Bipartite Iff No Odd Cycle

Exhibiting a valid split confirms that one particular graph is bipartite. A general test comes from a theorem. A graph is bipartite if and only if it contains no cycle of odd length. Here's the forward direction. In a bipartite graph, every edge crosses between the parts. So as you go around any cycle, consecutive vertices must alternate parts. If the first vertex is in part one, then every even-numbered vertex is in part one, and every odd-numbered one in part two. The cycle closes back at its start, which is in part one. So its length must be even. That means a bipartite graph can't have an odd cycle. The converse is also true. Its proof builds the split directly from a breadth-first traversal.

Example 9.3.2

A 5-Cycle Can't Be Split

Apply the theorem to a five-cycle, with edges A B, B C, C D, D E, and E A. Its length is five, which is odd. So it isn't bipartite. Check it directly. Try two colors, alternating from A. A gets color one, B color two, C color one, D color two, and E color one. That puts E and A in the same color. But E A is an edge. So no valid split into two parts exists.

Definitions 9.3.3 and 9.3.4

Regular and Null Graphs

Complete and bipartite graphs are defined by which edges are present. A regular graph is defined by degree instead. A graph is k-regular if every vertex has degree exactly k. The complete graph K n is n minus one regular. The null graph on n vertices has n vertices and no edges at all. It's also called the empty or edgeless graph. One note on terms. A few sources reserve null graph for the graph with no vertices either. Here, null and empty both mean edgeless. Both matter in engineering. If every spine switch connects to the same number of leaves, no spine becomes a disproportionate bottleneck, and a single failure behaves predictably. And the null graph models the network before any cabling decisions. Four switches, zero links, is a genuine starting point, with edges added over time.

Example 9.3.3

The 5-Cycle Is 2-Regular

Take the five-cycle again. Each vertex is adjacent to exactly its two neighbors along the cycle. So every degree is two, and the graph is two-regular. The handshake lemma gives a check that doesn't need the edge list. For a k-regular graph on n vertices, the degrees add to n times k, which is twice the edge count. So the number of edges is n k over two. Here that's five times two, over two, which is five. That matches the five edges. The null graph on four vertices is a boundary case worth checking. Every vertex has degree zero, so it's zero-regular. It's also trivially bipartite. Any split into two parts works, since there are no edges to break the rule.

Definition 9.3.5

Multigraphs

Every definition so far allowed at most one edge between a pair of vertices. The redundant cabling needs more. In a multigraph, a function assigns each edge a pair of endpoints. But the function needn't be one-to-one. Several different edges can be assigned the same pair. Those are parallel edges. The multiplicity of a pair u, v, written mu of u, v, counts the edges joining them. A simple graph is just a multigraph where every multiplicity is at most one. Conventions vary, so here's this course's. Multigraphs here have no loops. A graph with both loops and parallel edges is called a pseudograph, and isn't covered. Each parallel edge counts separately at both of its ends. So the handshake lemma still holds.

Example 9.3.4

A Link-Aggregation Pair

Here's an example. A leaf switch L connects to two spines, S one and S two. The team runs two cables from L to S one, for extra bandwidth. That's a link aggregation pair, configured with a protocol such as L A C P. And one cable runs from L to S two. So the multiplicity of L and S one is two, and of L and S two is one. L has degree three, S one has two, and S two has one. They add to six, twice the three edges, so the handshake lemma checks out. Notice that L has degree three, but only two distinct neighbors. That gap between degree and neighbor count can't happen in a simple graph.

Figure 9.3.1

4 Types Side by Side

Here are four of the types side by side. K four has every possible edge, six in all. K two comma three has edges only between its two parts, and it has no odd cycle. The five-cycle has every degree equal to two. And the multigraph has two parallel edges between L and S one. None of these records how strong or costly a connection is. A weighted graph attaches a number to each edge, like a link's latency or a cable's bandwidth. That comes later in the course.

Table 9.3.1

The Types Compared

This table compares the types. A complete graph has every pair adjacent, n times n minus one over two edges, and is n minus one regular. A complete bipartite graph has every cross-part pair adjacent, and none within a part. It has m times n edges, and it's regular only when m equals n. A k-regular graph has n k over two edges. The null graph has none, and is zero-regular. And a multigraph's edge count is the sum of its multiplicities, with the usual degree rules. These categories describe one graph in isolation. When two differently drawn graphs are really the same structure is a separate question, called isomorphism, taken up in section nine point four.

Takeaways

Shapes With Names

To summarize. A complete graph K n has every possible edge, n choose two of them, and every degree is n minus one. A bipartite graph splits into two parts with all edges between them. And a graph is bipartite exactly when it has no odd cycle. A k-regular graph has every degree equal to k, and the null graph is the zero-regular case. Multigraphs track parallel edges with their multiplicities. Here's something to think about. Complete and complete bipartite both mean every allowed edge is present. Could one graph be both at once? For n at least three, K n contains a triangle, since any three vertices are pairwise adjacent. What does the odd-cycle theorem say about that? Then push the reasoning down to the smallest cases, n equal to one and two. Are the two categories overlapping, disjoint, or somewhere in between?

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 Types of Graphs and Their Properties

How many edges does a complete graph K_n have?
A complete graph K_n has \binom{n}{2} = \frac{n(n-1)}{2} edges. Every vertex has degree n-1, so the degrees sum to n(n-1), which equals twice the edge count by the handshake lemma. For example, K_5 has \frac{5\cdot 4}{2}=10 edges, matching the number of unordered pairs of vertices.
How do you use the odd-cycle theorem to test whether a graph is bipartite?
A graph is bipartite if and only if it contains no cycle of odd length, so look for an odd cycle. In a bipartite graph, vertices alternate between the two parts around any cycle, which forces even length. The 5-cycle has length 5, so it is not bipartite. Two-coloring it fails because E and A get the same color.
What is a regular graph, and how many edges does a k-regular graph have?
A graph is k-regular if every vertex has degree exactly k. With n vertices, the degrees sum to nk, which equals twice the edge count, so there are \frac{nk}{2} edges. The 5-cycle is 2-regular, giving \frac{5\cdot 2}{2}=5 edges. The null graph, which has no edges, is 0-regular.
What is a multigraph, and how is it different from a simple graph?
A multigraph allows parallel edges, meaning several different edges can join the same pair of vertices. The number of edges joining u and v is the multiplicity \mu(u,v). A simple graph is a multigraph where every multiplicity is at most 1. Each parallel edge counts separately in a vertex's degree, so the handshake lemma still holds.

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 →