Graph Applications and Spanning Trees

These flashcards cover key concepts related to graph applications, including definitions and theorems related to spanning trees and graph coloring.

Spanning tree

A connected subgraph of a graph G that is a tree, which includes all vertices of G.

Connected graph

A graph in which there is a path between every pair of vertices.

Chromatic number

The smallest number of colors needed to color a graph such that no two adjacent vertices share the same color.

k-coloring

A coloring of a graph that uses k different colors.

Bipartite graph

A graph that can be colored using only two colors, meaning it is 2-colorable.

Depth-first traversal

A method of traversing graphs where you explore as far as possible along each branch before backtracking.

Breadth-first traversal

A method of traversing graphs where you explore all the neighbors at the present depth prior to moving on to nodes at the next depth level.

K6, C5, C8

K6 is a complete graph on 6 vertices, C5 is a cycle graph with 5 vertices, and C8 is a cycle graph with 8 vertices.

Graph coloring

An assignment of colors to each vertex in a graph such that no two adjacent vertices have the same color.

Theorem on spanning trees

Every connected graph G has at least one spanning tree.