Math 101:5.1-5.4, 6.1-6.5

What is a loop

• two vertices connected by an edge

• an edge that connects a vertex with itself

• two or more edges connecting the same two vertices

• a vertex of degree 0

What is an isolated vertex

• two edges with a shared vertex

• the set of vertices of a graph

• a vertex of degree 0

• a vertex of degree 1

What is a Euler path

• a path that travels along each edge of a graph once and only once

• a path that visits each vertex of a connected graph once and only once

• A path that visits every edge and every vertex exactly once

What is a Hamilton Circuit

• A circuit that visits each vertex of a connected graph once and only once

• a circuit that travels along each edge of a graph once and only once

• same as a path but starting and ending at the same vertex

Euler’s Circuit Theorem: a connected graph has an Euler circuit if and only if all vertices are (a)  

Euler’s Path Theorem: a connected graph has an Euler path if and only it has (a)   odd vertices

What does semi-eulerization mean

• the process of duplicating edges in a graph to make it have all but two even vertices

• the process of duplicating edges in a graph to make it have all even vertices

• builds a Euler circuit edge by edge. Involves choosing a bridge of the yet-to-be traveled part of the graph only when there is no other choice

What is the degree of vertex B

• 2

• 3

• 4

• 5

Tags

CCSS.8.G.A.5

Identify the bridge

(a)  

What is the edge list for this graph?

• AB, AD, AC, CD, CB, CA, DB, DX, XZ, ZY, XY

• AB, AD, AC, CD, CB, DC, DX, XZ, ZY, XY

• AB, AD, AC, CD, CB, DB, DX, XZ, ZY, XY

• AB, AD, AC, CD, CB, DB, XZ, ZY, XY