Self-Assessment Quiz: Introduction to Graphs

Twenty questions to check your understanding of vertices, edges, degree, the handshaking lemma, graph types, and isomorphism. Answer from memory before opening the key. Aim for 16+.

Throughout, "graph" means a simple graph unless a question says otherwise.

Question 1

A graph $G = (V, E)$ is formally defined as a pair in which an edge is:

A) an ordered pair $(u, v)$ of vertices B) an unordered pair $\{u, v\}$ of distinct vertices C) a single vertex D) a path between two vertices

Question 2

The degree of a vertex $v$ in a simple graph equals:

A) the number of vertices in the graph B) the number of edges in the graph C) the number of edges incident to $v$ (equivalently $\lvert N(v)\rvert$) D) the length of the longest path from $v$

Question 3

A simple graph on $n$ vertices has at most how many edges?

A) $n$ B) $n - 1$ C) $\binom{n}{2} = \frac{n(n-1)}{2}$ D) $n^2$

Question 4

The handshaking lemma states that for any graph $G = (V, E)$:

A) $\sum_{v \in V} \deg(v) = \lvert E\rvert$ B) $\sum_{v \in V} \deg(v) = 2\lvert E\rvert$ C) $\sum_{v \in V} \deg(v) = \lvert V\rvert$ D) every vertex has even degree

Question 5

The handshaking lemma is proved by:

A) induction on the number of vertices B) contradiction C) double-counting the (vertex, edge) incidences D) the pigeonhole principle

Question 6

By the corollary to the handshaking lemma, the number of vertices of odd degree is always:

A) zero B) odd C) even D) equal to $\lvert E\rvert$

Question 7

Which degree sequence is impossible for a simple graph?

A) $(2, 2, 2)$ B) $(3, 3, 2, 2)$ C) $(3, 3, 3)$ D) $(1, 1)$

Question 8

In a directed graph, the in-degree $\deg^-(v)$ counts:

A) arcs leaving $v$ B) arcs entering $v$ C) all arcs touching $v$ D) the neighbors of $v$ in the undirected sense

Question 9

A graph is bipartite if and only if it:

A) is connected B) has no cycle of odd length C) is complete D) has an even number of vertices

Question 10

The complete graph $K_n$ has every vertex of degree:

A) $n$ B) $n - 1$ C) $2$ D) $\binom{n}{2}$

Question 11

The difference between a walk and a path is:

A) a walk must be closed; a path may not be B) a path may repeat vertices; a walk may not C) a path has no repeated vertex; a walk may repeat vertices D) there is no difference

Question 12

A graph is connected when:

A) every vertex has the same degree B) there is a path between every pair of vertices C) it has $\binom{n}{2}$ edges D) it contains no cycle

Question 13

Two graphs $G_1$ and $G_2$ are isomorphic ($G_1 \cong G_2$) when there is:

A) any function $f \colon V_1 \to V_2$ B) a bijection $f \colon V_1 \to V_2$ with $\{u,v\}\in E_1 \iff \{f(u),f(v)\}\in E_2$ C) the same number of vertices in each D) a path from every vertex of $G_1$ to every vertex of $G_2$

Question 14

Which of these is a valid way to prove two graphs are not isomorphic?

A) try all $n!$ relabelings and report none worked B) check that they have the same number of vertices C) exhibit a single invariant (e.g. degree sequence) on which they differ D) draw both and note they look different

Question 15

If two graphs have the same sorted degree sequence, you may conclude:

A) they are definitely isomorphic B) they are definitely not isomorphic C) they might be isomorphic — the test is necessary but not sufficient D) nothing at all about them

Question 16 (True/False, justify)

True or false: There is a simple graph in which exactly three vertices have odd degree. Justify in one sentence.

Question 17 (True/False, justify)

True or false: In a simple graph, $\deg(v) = \lvert N(v)\rvert$ for every vertex $v$. Justify in one sentence (and say where this can fail).

Question 18 (True/False, justify)

True or false: Friendship on a mutual-friends platform is best modeled with directed edges. Justify in one sentence.

Question 19 (Short answer)

A party has 6 guests, and each guest shakes hands with exactly 3 others. Is this possible? If so, how many handshakes occurred? Show the arithmetic.

Question 20 (Short answer)

State the four modeling questions (§27.6) you ask before building any graph.

Answer Key

Topics to review by question