Graph Theory

Which of the following is the correct formal definition of a graph?

• A collection of equations and inequalities

• A structure consisting of a set of vertices and a set of edges connecting them

• A function from vertices to numbers

• A sequence of numbers arranged in a table

What distinguishes a simple graph from a directed graph?

• A simple graph can have loops, while a directed graph cannot

• A simple graph has directions on edges, while a directed graph does not.

• A simple graph has undirected edges with no loops or multiple edges; a directed graph has edges with direction

• There is no difference

Which of the following diagrams represents a complete graph on 4 vertices?

• 
• 
• 
• None of the above

True or False: In a bipartite graph, each edge connects a vertex from one subset to a vertex in the same subset.

In the graph shown, what is the degree of vertex B?

• 2

• 3

• 4

• 5

The graph is connected and has four vertices of even degree. What can we conclude?

• It has an Eulerian circuit

• It has an Eulerian path but not a circuit

• It is a bipartite graph

• It cannot be traversed in one path

Which of the following statements about Hamiltonian paths is TRUE?

• A Hamiltonian path visits every edge exactly once

• A Hamiltonian path must begin and end at the same vertex

• A Hamiltonian path visits every vertex exactly once

• A Hamiltonian path only exists in complete graphs

A subgraph contains all the same vertices and edges from the original graph that connect them. What type of subgraph is this?

• Weighted subgraph

• Induced subgraph

• Bipartite subgraph

• Complete subgraph

In a directed graph, if a vertex has 3 incoming edges and 2 outgoing edges, what are its in-degree and out-degree, respectively?

• In-degree = 2, Out-degree = 3

• In-degree = 5, Out-degree = 0

• In-degree = 3, Out-degree = 2

• In-degree = 3, Out-degree = 5

Which of the following is not the property of the given graph?

• Disconnected

• Complete

• Bipartite

• Undirected