Online College Courses for Credit

Graphs, Connectedness, And Trees

Graphs, Connectedness, And Trees

Author: c o

To explore the concept of connectedness in graphs
To introduce the learner to spanning trees
To investigate the conditions underwhich a graph can be known to be connected

In this packet, we learn about connectedness and spanning trees in graphs.

See More

Try Our College Algebra Course. For FREE.

Sophia’s self-paced online courses are a great way to save time and money as you earn credits eligible for transfer to many different colleges and universities.*

Begin Free Trial
No credit card required

47 Sophia partners guarantee credit transfer.

299 Institutions have accepted or given pre-approval for credit transfer.

* The American Council on Education's College Credit Recommendation Service (ACE Credit®) has evaluated and recommended college credit for 33 of Sophia’s online courses. Many different colleges and universities consider ACE CREDIT recommendations in determining the applicability to their course and degree programs.



This packet continues where this introduction to graph theory left off.  If you have no previous experience with graph theory, you ought to go over the previous lesson.

Just in case you need a little refresher, the following list gives brief definitions of some of the terms used in this packet:

  • path: a set collection of edges leading from one vertex to another
  • cycle: a path that leads back to its starting point never having crossed the same edge twice
  • connected: a graph is connected when there is a path between any two vertices; if there exist two vertices for which no path can be formed between, the the graph is not connected.
  • tree: a connected graph with no cycles
  • adjacent: two vertices are called adjacent when they share an edge
  • degree: the degree of a vertex is the number of edges with which it is incident

Trees And Connected Graphs

IN this video, we work our way up to showing that every connected graph contains a spanning subtree.

Exploring Connectedness

In this video, we look at a criterion which is sufficient (but not necessary) to show that a graph is connected.