Question bank — Graph definitions — directed, undirected, weighted, unweighted, simple, multigraph

False in general. Modelling one undirected edge as two arcs does double the count, but a directed graph is defined independently — it can have any number of arcs, including just one, so no fixed "twice" rule holds.

False. They are the same connectivity but not the same object: the undirected version is one edge, the directed pair is two edges, so $m$ differs and your adjacency list stores different counts.

False. "Simple" is a rule (no self-loops, no parallel edges), not a size. A simple graph can be the dense complete graph $K_n$ with $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges — the maximum possible.

True. A multigraph just relaxes two rules (allows parallel edges and self-loops); it is still a set of vertices and edges, so it satisfies the general definition $G=(V,E)$.

True. "Multigraph" permits parallel edges and self-loops but does not require them, so a simple graph is the special case where none happen to occur.

False. An unweighted graph is a weighted graph with every weight $=1$; plain BFS finds shortest paths on it, and faster than Dijkstra because all edges cost the same.

True only if the graph is not simple. In a simple undirected graph the max degree is $n-1$ (connect to every other vertex), but self-loops or parallel edges push a multigraph's degree higher.

False. It holds for every undirected graph, connected or not, because it counts edge-ends and each edge contributes exactly $2$ ends regardless of connectivity.

False. Since $\sum \mathrm{deg}(v)=2m$ is even, the odd-degree contributions must sum to something even, which forces the count of odd-degree vertices to be even.

False. Weights can be zero or negative (e.g. money gained). The definition allows any number; only specific algorithms (like Dijkstra) additionally require non-negative weights.

False. A self-loop $(v,v)$ is exactly one of the two things "simple" forbids, so the graph immediately becomes a multigraph.

True. Simple only bans duplicate identical edges and self-loops; $(u,v)$ and $(v,u)$ are two different ordered pairs, so both may coexist in a simple directed graph.

Two errors: the repeated $A-B$ is a parallel edge, so it is a multigraph, not simple; and $m=2$ because both edges count.

That is the directed count. Undirected pairs $\{u,v\}$ and $\{v,u\}$ are the same edge, so you divide by $2$: $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$.

It adds $2$. Both ends of the loop attach to the same vertex, and degree counts edge-ends, so a self-loop contributes $2$ (keeping the handshaking lemma exact).

Dropping the second road discards real information (different lengths/costs). The correct model is a multigraph that keeps both parallel edges; "simple" is not a goal to force here.

It only works on directed graphs (and specifically ones with no directed cycles). See Topological sort — an undirected edge has no "before/after", so ordering is undefined.

Ambiguous/wrong. Directed vertices have two degrees: in-degree (arrows in) and out-degree (arrows out); a single $\mathrm{deg}(v)$ is not defined without saying which.

Because an undirected edge is an unordered pair, so $\{u,v\}$ and $\{v,u\}$ are counted twice among ordered choices and must be halved; directed arcs $(u,v)\ne (v,u)$ are genuinely distinct, so no halving.

Topological sort orders vertices so every edge points "forward"; that only makes sense when edges have a forward direction. Undirected edges carry no order, so no such ordering exists.

Setting all weights to $1$ is a valid, information-preserving special case; but flattening distinct weights to $1$ erases the costs the algorithm needed, so "cheapest path" collapses into "fewest hops".

It keeps only "who connects to whom" and throws away domain specifics, so friendships, roads, and web links all become the same structure that BFS or Dijkstra can process.

Each undirected edge $\{u,v\}$ is listed in both $u$'s neighbours and $v$'s neighbours, so every edge appears twice across the adjacency list.

A tree is connected and acyclic; a self-loop or a parallel edge would create a cycle, contradicting acyclicity, so neither can appear.

Both give $0$ edges. With $0$ or $1$ vertex there is no distinct pair to connect, so the maximum (and only) edge count is zero.

Yes. $G=(\{v\},\varnothing )$ is a legal graph with $n=1,m=0$; graphs are allowed to have an empty edge set.

Only if it has at most one vertex. With two or more isolated vertices and no edges, no path links them, so it is disconnected — but it is still a perfectly valid graph.

Yes. Weights are just labels on edges; distinct edges may freely share a value, and this does not make them parallel (parallel means same endpoints).

Exactly $0$, since $\sum \mathrm{deg}(v)=2m=2\cdot 0$. Every vertex is isolated with degree $0$.

Yes — an isolated vertex with no arrows in or out. It still belongs to $V$ and is a legitimate part of the directed graph.