Fundamentals of Graph Terminology Quiz

1) Two edges sharing a common vertex are called adjacent edges.

True

False

Adjacent edges meet at a shared vertex.

Explanation

Adjacent edges meet at a shared vertex.

2) A complete graph is one where every pair of distinct vertices is connected by an edge.

True

False

That is the definition of a complete graph.

Explanation

That is the definition of a complete graph.

3) A graph with no edges is called a:

Path

Null graph

Cycle

Tree

A null graph has only isolated vertices.

Explanation

A null graph has only isolated vertices.

4) A cycle is a closed walk with no repeated edges and no repeated vertices (except start/end).

True

False

A cycle returns to its start without repeating internal vertices.

Explanation

A cycle returns to its start without repeating internal vertices.

5) In a simple graph, two vertices with the same degree are called:

Twins

Leaves

Balanced

Regular

Vertices with equal degree may be referred to as twins.

Explanation

Vertices with equal degree may be referred to as twins.

6) The complement of a simple graph is the graph that:

Has the same edges reversed

Has every possible edge of

Includes edges not present in between existing vertices

Has no edges

The complement contains exactly the missing edges.

Explanation

The complement contains exactly the missing edges.

7) A graph is called simple if it:

Has no cycles

Has no loops or multiple edges

Has exactly two components

Has only one vertex

Simplicity means no repeated edges or loops.

Explanation

Simplicity means no repeated edges or loops.

8) A walk in a graph allows:

No repeated edges

No repeated vertices

Repetition of vertices and edges

Only repeated vertices

Walks may repeat vertices and edges.

Explanation

Walks may repeat vertices and edges.

9) A trail is a walk with:

No repeated vertices

No repeated edges

No cycles

No leaves

Trails cannot repeat edges.

Explanation

Trails cannot repeat edges.

10) A connected graph with no cycles is called a:

Cycle graph

Tree

Multigraph

Path graph

A tree is acyclic and connected.

Explanation

A tree is acyclic and connected.

11) A spanning subgraph contains all vertices of the original graph.

True

False

“Spanning” means including every vertex.

Explanation

“Spanning” means including every vertex.

12) The number of vertices in a graph is called its:

Order

Size

Degree

Rank

Order = number of vertices.

Explanation

Order = number of vertices.

13) The number of edges in a graph is called its:

Order

Size

Weight

Capacity

Size = number of edges.

Explanation

Size = number of edges.

14) Vertices that have degree 1 are called:

Roots

Leaves

Centers

Ends

A degree-1 vertex is a leaf.

Explanation

A degree-1 vertex is a leaf.

15) Which graphs are always bipartite?

Trees

Even cycles

Odd cycles

Complete graphs

Odd cycles are not bipartite.

Explanation

Odd cycles are not bipartite.

Submit

Fundamentals of Graph Terminology Quiz

1) Two edges sharing a common vertex are called adjacent edges.

2)

What first name or nickname would you like us to use?

2) A complete graph is one where every pair of distinct vertices is connected by an edge.

3) A graph with no edges is called a:

4) A cycle is a closed walk with no repeated edges and no repeated vertices (except start/end).

5) In a simple graph, two vertices with the same degree are called:

6) The complement of a simple graph is the graph that:

7) A graph is called simple if it:

8) A walk in a graph allows:

9) A trail is a walk with:

10) A connected graph with no cycles is called a:

11) A spanning subgraph contains all vertices of the original graph.

12) The number of vertices in a graph is called its:

13) The number of edges in a graph is called its:

14) Vertices that have degree 1 are called:

15) Which graphs are always bipartite?