09 Introduction to Graph Theory Online Quiz Questions

For a simple undirected graph, the adjacency matrix is symmetric.

A simple undirected graph has edges $xy$, $xz$, and $xw$ incident with vertex $x$, and no other edge incident with $x$. What is $\deg(x)$?

Let $G$ have vertex set $V=\{a,b,c,d\}$ and edge set $E=\{ab,bc,cd\}$. Which graph is a spanning subgraph of $G$?

Which statements correctly describe graph representations or their uses? Select all that apply.

If a graph is connected, then there is exactly one path between every pair of vertices.

A graph has edges $uv$, $vw$, $wz$, and $vz$. What is the distance $d(u,z)$, measured as the number of edges in a shortest path?

A simple graph has edges $ab$, $bc$, $cd$, $da$, and $ac$. Which sequence is a cycle?

In an undirected graph, a loop contributes 2 to the degree of its incident vertex.

A graph has vertex set $\{a,b,c,d,e,f\}$ and edge set $\{ab,bc,de\}$. Select all of its connected components, giving each component by its vertex set.

Explain the difference between a spanning subgraph and an induced subgraph. Include what each must retain from the original graph and why a subgraph with the same selected vertices might fail to be induced.

In an incidence matrix for a simple undirected graph, what does one column represent?

A simple undirected graph is represented by an adjacency matrix. Which property must the matrix have?

For the graph $V=\{a,b,c,d\}$ with $E=\{ab,ac,bc,cd\}$, which is the degree sequence when written in nonincreasing order?

A graph has vertex set $\{a,b,c,d,e\}$ and edges $ab,bc,de$. How many connected components does it have?

In a graph containing the edges $ab$ and $bc$, how should the vertex sequence $a,b,c,b$ be classified?

Which graph representation is usually efficient for a sparse graph because it records only the neighbors that each vertex actually has?

Let $G$ have $V=\{a,b,c,d\}$ and $E=\{ab,ac,bc,cd\}$. Which edge set must the subgraph induced by $W=\{a,b,c\}$ contain?

Which number of odd-degree vertices could a finite undirected graph have?