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
Introduction to Psychology

Analyze this:
Our Intro to Psych Course is only $329.

Sophia college courses cost up to 80% less than traditional courses*. Start a free trial now.



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.