+

# Graphs, Connectedness, And Trees

(0)
Author: c o
##### Description:

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.

(more)

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.*

No credit card required

28 Sophia partners guarantee credit transfer.

281 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 25 of Sophia’s online courses. Many different colleges and universities consider ACE CREDIT recommendations in determining the applicability to their course and degree programs.

Tutorial

## Introduction

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.