Graph Theory Quiz

What is a graph?

• A set of points connected by lines, where the lines can be curved or straight.

• A mathematical structure consisting of two finite sets V (vertices) and E (edges), where each edge has one or two vertices as endpoints.

• A collection of nodes and arcs, where arcs can only connect two distinct nodes.

• A visual representation of data using bars or lines.

What is a simple graph?

• A graph with no edges.

• A graph that has neither self-loops nor multiple edges.

• A graph where all vertices have the same degree.

• A graph that can be drawn without crossing edges.

What is a loop in a graph?

• An edge that connects two distinct vertices.

• An edge that joins a single vertex to itself.

• A cycle that includes all vertices in the graph.

• A path that starts and ends at the same vertex.

What is a multi-edge?

• A collection of two or more edges having identical endpoints.

• An edge that connects more than two vertices.

• A path that includes multiple edges.

• A graph with multiple connected components.

What is the neighborhood of a vertex v in a graph G?

• The set of all vertices in G that are not connected to v.

• The set of all vertices in G that are connected to v by an edge.

• The set of all edges in G that are incident to v.

• The set of all vertices in G that are at a distance of 2 from v.

What is a directed edge (or arc) in a digraph?

• An edge that connects two vertices without any direction.

• An edge where one endpoint is designated as the tail and the other as the head.

• An edge that forms a cycle in the graph.

• An edge that connects a vertex to itself.

What is a digraph?

• A graph where all edges are directed.

• A graph that contains both directed and undirected edges.

• A graph that has no cycles.

• A graph where all vertices have the same indegree and outdegree.

What is the indegree of a vertex in a digraph?

• The number of edges directed away from the vertex.

• The number of edges directed towards the vertex.

• The total number of edges connected to the vertex.

• The number of cycles that include the vertex.

What is the outdegree of a vertex in a digraph?

• The number of edges directed away from the vertex.

• The number of edges directed towards the vertex.

• The total number of edges connected to the vertex.

• The number of cycles that include the vertex.

What is a bipartite graph?

• A graph where the vertices can be divided into two disjoint sets such that no two vertices in the same set are adjacent.

• A graph that contains only even-length cycles.

• A graph where all vertices have the same degree.

• A graph that can be drawn without crossing edges.