Network Connectivity, Graph Theory, and Reliable Network Design

Overall rating: 4.88 Instructor: 4.88 Materials: 5.00 more …

Network engineers are tasked with designing reliable networks while balancing business and physical concerns such as cost and available space. Reliable networks are designed to ensure packets can still reach required destinations even upon a node or router failure. At the design level, how do we ensure a network is “connected” enough to provide a required number of alternative paths from any node to any other node?

Mathematicians, electrical engineers, and early network engineers studied this problem using graph theory. We have a formal definition of the measure of connectivity of a graph or network that also allow us to determine the “weak points” whose failure would sever the network into 2 or more separated blocks. In this webinar, the attendee will be introduced to the terminology and study of graph theory in context with these engineering questions in order to develop a new perspective and skill set he/she can apply to his day-to-day work (no background in mathematics or graph theory is required).

We will begin with the definition of a graph, and other basic terminologies such as the degree of a vertex, connected graphs, paths, and complete graphs. Next, we will move to a discussion of connectivity. The attendee will learn what a cut-vertex is, and several ways of finding them in a network. The notion of a nonseparable graph will be mentioned, and we will discuss how we can know if a given network is nonseparable. These fundamentals will enable us to understand what the connectivity measure of a graph is, its relation to the resilience and reliability of a network. We will also look at using powers of graphs to add edges to achieve the desired level of connectivity per given requirements.


This webinar is part of Internetworking roadmap and accessible with standard subscription

Start now Access content


Intro: Why we care about graph theory and connectivity

Graph Basics:

  • What is a graph?
  • What are the parts of a graph?
  • How do we get around on graphs?
  • What does it mean to say a graph is connected?
  • What is the degree of a graph?
  • What is a complete graph?


  • What is a cut-vertex? What does it mean if we have one in our network? How do we find these?
  • Nonseparable graphs — How do we know if our network is nonseparable? Can we make a network nonseparable?
  • Vertex connectivity and its relation to reliability and resilience of a network
  • How do we determine the maximum connectivity graphs? (Intro to Harary graphs)
  • Using powers of graphs to add edges to achieve connectivity requirements


The key takeaways for the attendees will be

  • New familiarity with a mathematical topic highly applicable to his field (and partially developed as a result of questions posed in early network engineering)
  • An understanding of what connectivity in networks means mathematically
  • A new perspective on network design


Rachel TraylorDr. Rachel Traylor is a professional private-sector mathematician and the cofounder of the Math Citadel, a research and consulting firm specializing in mathematical consulting. She received her PhD in mathematics from the University of Texas at Arlington, a MS Statistics and BS Applied Mathematics from Georgia Tech. Her research interests include probability theory, reliability, and queuing theory; in particular, she’s been very interested in sequences of dependent random variables. She’s a former senior research scientist for Dell EMC, former university lecturer in mathematics and statistics (Foothill College, University of Texas at Arlington, Georgia Tech), and former DBA/Quality Analyst at Lockheed Martin. She has 6 pending patents and 9 academic publications in the fields of probability and reliability theory.

More about Rachel…

Happy Campers

About the webinar

it would be good to hear a similar talk on the different algorithms related to networking (eg. SPF)

Mark Horsfield
This just scratched the surface; I would love to see more material that dives deeper into various areas mentioned during the webinar. Great content, I really enjoyed it!
Just about everything that happens in networking involves math in some form or another. We may not directly interact with the math very much, but knowing how it works is what I consider to be a portion of foundational knowledge that every good network architect/engineer should possess.
Bruno Wollmann
It was a great session. Up until this session I had foundation knowledge on the topic. A great start and look forward to another session on this topic
Michael Sifuentes
Few of my fellow network/system engineers have a solid background in CS (myself included). Sessions like this one inform us about fundamental concepts that are the foundation of the technologies we work with. I look forward to learning more in future sessions!
Daniel Justice


Great webinar this morning with @ioshints featuring @MathCitadel discussing network connectivity, graph theory, and reliable network design. It was time well spent on a holiday Monday in Canada. I’m looking forward to more of these in the future.