True/False Indicate whether the
statement is true or false.


1.

Mathematically, a graph is a set V of vertices and a set E of
edges, such that each edge in E connects three of the vertices in V.


2.

Vertices and edges can be labeled or unlabeled.


3.

Two adjacent vertices are also called neighbors.


4.

A vertex is reachable from another vertex if and only if there is a path between
the two.


5.

The weight of a path is the number of edges on the path.


6.

A child of a given graph consists of a subset of that graph’s vertices and
the edges connecting those vertices.


7.

A simple path is a path that does not pass through the same vertex more than
once.


8.

A loop is a path that begins and ends at the same vertex.


9.

Each edge in a digraph is called a directed edge.


10.

Lists and trees are special cases of undirected graphs.

Multiple Choice Identify the
choice that best completes the statement or answers the question.


11.

We can use the term ____ as a synonym for vertex.
a.  node  c.  index  b.  element  d.  bucket 


12.

When the edges are labeled with numbers, the graph is said to be a(n) ____
graph.
a.  directed  c.  weighted  b.  undirected  d.  labeled 


13.

One vertex is ____ to another vertex if there is an edge connecting the two
vertices.
a.  contiguous  c.  parent  b.  related  d.  adjacent 


14.

A ____ is a sequence of edges that allows one vertex to be reached from another
vertex in a graph.
a.  route  c.  link  b.  path  d.  chain 


15.

A graph is ____ if there is a path from each vertex to every other
vertex.
a.  directed  c.  weighted  b.  connected  d.  complete 


16.

A graph is ____ if there is an edge from each vertex to every other
vertex.
a.  directed  c.  weighted  b.  connected  d.  complete 


17.

The ____ of a vertex is equal to the number of edges connected to it.
a.  degree  c.  label  b.  weight  d.  level 


18.

A ____ is a subgraph consisting of the set of vertices that are reachable from a
given vertex.
a.  cycle  c.  connected component  b.  digraph  d.  child 


19.

The edges of a(n) ____ have no direction.
a.  simple graph  c.  cycle  b.  undirected graph  d.  digraph 


20.

The edges in a(n) ____ specify an explicit direction.
a.  simple graph  c.  cycle  b.  undirected graph  d.  digraph 
