Graph Theory Review: Lessons 1-4

​Order = # of vertices

Length = # of edges crossed in a path

Distance = shortest path length between two points

Degree = number of edges touching a vertex

Using the graph below,

degree of 4 = 3

degree of 6 = 1

Order = 6

Length of path 643 = 2 edges

Length of path 6451 = 3 edges

d(6,3) = 2 edges

d(5,1) = 1 edge

​Definitions Review:

Multiple Choice

What is the degree of Vertex D?

• 1

• 2

• 3

• 4

• 5

Multiple Choice

What is the order of this graph?

• 1

• 5

• 3

• 4

Multiple Choice

What is the length of path 13252?

• 1

• 2

• 3

• 4

Multiple Choice

What is the distance from F to B?

• 1

• 2

• 3

• 4

Path/Chain = A series of vertices connected via edges.

Cycles/Circuits = A path that starts and ends at the same vertex.

Simple = A path/circuit with no repeated edges

​

Paths and Cycles

​Using the graph below,

ABCD is a path

ABCDEA is a cycle

ABC is a simple path

ABEA is a simple cycle

ABCB is NOT a simple path

Multiple Choice

Which of the following is not a CIRCUIT in the graph?

• ADCDEDA

• CADC

• EDCCE

• ADECA

• All of the above are circuits

Multiple Select

Check all of the paths from A to G.

Select exactly 3 ANSWERS.

• ADEEBFG

• ABFHG

• ADCBFG

• ABFG

• ABCBFG

Multiple Choice

A path that starts and ends at the same vertex and does not repeat any edges. What am I?

• simple circuit

• path

• simple path

• length

Multiple Choice

Is the path 1234 a simple path?

• Yes

• No

Euler Path = Cross ALL edges once

• Must be a connected graph

• Exactly two vertices have an odd degree

• Start and end at these two odd-degree vertices

​

​Types of Paths

Hamilton Path = Cross ALL vertices once

• Must be a connected graph

• Doesn't matter where you start or end

Using the graph below,

Euler Path = BAEDCBE

Hamilton Path = ABCDE

Multiple Choice

Euler paths must touch

• all edges

• all vertices

Multiple Choice

Hamilton touches

• all edges

• all vertices

Multiple Choice

This graph will have a Euler's Path. 

• True

• False

Multiple Choice

How do we quickly determine if the graph will have a Euler's Path

• All even degree verticies

• Exactly 2 odd degree verticies

• Each vertex will be used once

• I have no clue. 

Multiple Choice

Touching ALL VERTICES in a graph without repeating, and starting and stopping at different spots

• Euler Circuit

• Euler Path

• Hamilton Circuit

• Hamilton Path

Euler Cycle = Cross ALL edges

• Must be connected

• All vertices must have EVEN degrees

• Start and end at the same vertex

​

Types of Cycles

​Hamilton Cycle = Cross ALL vertices

• Must be connected

• All vertices must have degrees greater than 1

​Using the graph below,

Euler Cycle= ABCDEACEBDA

Hamilton Cycle = ABCDEA

Multiple Choice

Which of the following is a Hamilton circuit of the graph?

• ABCDEFGA

• ACBEGFDA

• CBGEDFAC

• CEGBADFC

Multiple Choice

Crossing ALL edges in a graph while starting and stopping at the same vertex is....

• Euler Circuit

• Euler Path

Multiple Choice

Circuits start and stop at 

• same vertex

• different vertices

Multiple Choice

Crossing ALL VERTICES in a graph without repeating and starting and stopping at same vertex is....

• Euler Circuit

• Euler Path

• Hamilton Circuit

• Hamilton Path

Multiple Choice

This graph will have a Euler's Circuit

• True

• False

Multiple Choice

How do we quickly determine if a graph will have a Euler's Circuit? 

• All even degree verticies

• Exactly 2 odd degree verticies

• Every Vertex will be used once

• I have no clue

Multiple Choice

A graph has the vertices with the following degrees: 4, 6, 8, 2, 2, 6, 4
What do we DEFINITELY KNOW?

• This will have a Euler's Circuit

• This will have a Euler's Path

• This will have a Hamiltonian Path

• We need more information