Graph Theory Basics

Which set represents the vertices of the graph?

• {1,2}, {2,3}. {2,4}, {4,5}, {4,6}

• {1, 2, 3, 4, 5, 6,}

• {1, 2, 3, 4, 5, 6, 7}

• {1,2}, {2,3}. {2,4}, {4,5}, {4,6}, {6,7}

What is the degree of vertex 4?

• 3

• 4

• 5

• 7

Which two vertices are adjacent vertices?

• 5 is adjacent to 6

• 3 is adjacent to 6

• 4 is adjacent to 1

• 3 is adjacent to 2

A loop in a graph is ...

• A circle

• the edge - the two end-points of which are the same

• no edge incident with the point

• More than one edge between two points

The sum of degrees of the points in every graph is ...

• is an odd number

• Is an even number

• twice the number of edges

• the half of the number of edges

Tracing all edges on a figure without picking up your pencil or repeating edges and starting and stopping in the same spot

• Euler Circuit

• Euler Path

Tracing all edges on a figure without picking up your pencil or repeating edges and starting and stopping at different spots

• Euler Circuit

• Euler Path

Which of the following is false?

• Euler Paths exist when there are exactly two vertices of odd degree.
• Euler circuits exist when the degree of all vertices are even.
• A graph with more than two odd vertices will never have an Euler Path or Circuit.
• A graph with one odd vertex will have an Euler Path but not an Euler Circuit.

Does this graph have an Euler Path, Euler Circuit, both, or neither?

• Euler Path
• Euler Circuit
• Both
• Neither

Is the following graph connected?

• Yes

• No