Advanced Graph Terminology

1) The in-degree of a vertex v is:

Number of edges leaving v

Number of edges entering v

Sum of all edge weights incident on v

Number of loops at v

The in-degree of a vertex v is the number of edges entering v because each incoming directed edge contributes one to its in-degree while edges leaving v count toward out-degree, and a loop counts once as incoming and once as outgoing since it begins and ends at v.

Explanation

The in-degree of a vertex v is the number of edges entering v because each incoming directed edge contributes one to its in-degree while edges leaving v count toward out-degree, and a loop counts once as incoming and once as outgoing since it begins and ends at v.

2) A graph is bipartite if and only if it contains no odd cycle.

True

False

A graph is bipartite if and only if it contains no odd cycle because any odd-length cycle prevents the vertices from being split into two independent sets without forcing an edge to lie within a set, while conversely any graph free of odd cycles can always be two-colored, which is exactly the condition for bipartiteness.

Explanation

A graph is bipartite if and only if it contains no odd cycle because any odd-length cycle prevents the vertices from being split into two independent sets without forcing an edge to lie within a set, while conversely any graph free of odd cycles can always be two-colored, which is exactly the condition for bipartiteness.

3) A complement graph G′ of G is formed by:

Adding edges that are in G

Removing all edges

Connecting every non-adjacent pair of vertices in G

Keeping the same edge set

The complement graph G′ of a graph G is formed by connecting every non-adjacent pair of vertices in G, meaning G′ has the same vertex set as G but replaces non-edges with edges and edges with non-edges so that (u, v) is an edge in G′ exactly when it is not an edge in G.

Explanation

The complement graph G′ of a graph G is formed by connecting every non-adjacent pair of vertices in G, meaning G′ has the same vertex set as G but replaces non-edges with edges and edges with non-edges so that (u, v) is an edge in G′ exactly when it is not an edge in G.

4) Every tree is a connected graph with no cycles.

True

False

The statement “Every tree is a connected graph with no cycles” is true because a tree is defined precisely as an acyclic connected graph, and this property ensures that adding any edge to a tree would create a cycle while removing any existing edge would break its connectivity.

Explanation

The statement “Every tree is a connected graph with no cycles” is true because a tree is defined precisely as an acyclic connected graph, and this property ensures that adding any edge to a tree would create a cycle while removing any existing edge would break its connectivity.

5) A connected graph with n vertices and n edges must be a tree.

True

False

A connected graph with n vertices and n edges is not a tree because a tree must have exactly n − 1 edges, so having n edges means there is at least one additional edge beyond the minimal number required for connectivity, guaranteeing the existence of a cycle.

Explanation

A connected graph with n vertices and n edges is not a tree because a tree must have exactly n − 1 edges, so having n edges means there is at least one additional edge beyond the minimal number required for connectivity, guaranteeing the existence of a cycle.

6) In a directed graph, the sum of all in-degrees equals the sum of all out-degrees.

True

False

In a directed graph the sum of all in-degrees equals the sum of all out-degrees because each directed edge contributes exactly one out-degree to its tail vertex and one in-degree to its head vertex, making both totals equal to the number of directed edges |E| when summed over the entire vertex set.

Explanation

In a directed graph the sum of all in-degrees equals the sum of all out-degrees because each directed edge contributes exactly one out-degree to its tail vertex and one in-degree to its head vertex, making both totals equal to the number of directed edges |E| when summed over the entire vertex set.

7) The complement of a complete graph Kₙ is an empty graph (no edges).

True

False

The complement of a complete graph Kₙ is an empty graph because Kₙ already contains every possible edge between its n vertices, leaving no missing edges for the complement to include, so the complement must contain zero edges.

Explanation

The complement of a complete graph Kₙ is an empty graph because Kₙ already contains every possible edge between its n vertices, leaving no missing edges for the complement to include, so the complement must contain zero edges.

8) Two graphs G₁ and G₂ are said to be isomorphic if they have the same number of vertices and edges.

True

False

Two graphs G₁ and G₂ are not necessarily isomorphic merely because they have the same number of vertices and edges, since isomorphism also requires a one-to-one correspondence between vertices that preserves adjacency, meaning the connectivity structure of the graphs must match exactly and not just their counts.

Explanation

Two graphs G₁ and G₂ are not necessarily isomorphic merely because they have the same number of vertices and edges, since isomorphism also requires a one-to-one correspondence between vertices that preserves adjacency, meaning the connectivity structure of the graphs must match exactly and not just their counts.

9) Weighted graphs are always directed.

True

False

Weighted graphs are not always directed because weights can be assigned to edges in either directed or undirected settings, such as undirected road networks where distances or travel times label edges, so the presence of weights does not imply direction.

Explanation

Weighted graphs are not always directed because weights can be assigned to edges in either directed or undirected settings, such as undirected road networks where distances or travel times label edges, so the presence of weights does not imply direction.

10) In a directed graph (digraph), each edge is represented as:

An ordered pair (u, v)

An unordered pair {u, v}

A weighted pair (u, v, w)

A bidirectional pair

In a directed graph, each edge is represented as an ordered pair (u, v) because direction matters, meaning the edge starts at u and points to v, unlike undirected edges that use unordered pairs {u, v}, and although weights may be added in weighted digraphs, the essential representation is the ordered pair indicating direction.

Explanation

In a directed graph, each edge is represented as an ordered pair (u, v) because direction matters, meaning the edge starts at u and points to v, unlike undirected edges that use unordered pairs {u, v}, and although weights may be added in weighted digraphs, the essential representation is the ordered pair indicating direction.

11) Identify the correct relation for a regular graph of degree r and n vertices.

Each vertex has degree r, total edges = n × r

Total edges = n × r / 2

Each vertex connects to all others

Graph must be complete

For a regular graph of degree r with n vertices, each vertex has degree r and the total number of edges is n × r divided by 2 because summing all degrees gives n × r, and by the Handshaking Lemma this must equal 2|E|, so |E| = (n r)/2, with complete graphs appearing as the special case where r = n − 1.

Explanation

For a regular graph of degree r with n vertices, each vertex has degree r and the total number of edges is n × r divided by 2 because summing all degrees gives n × r, and by the Handshaking Lemma this must equal 2|E|, so |E| = (n r)/2, with complete graphs appearing as the special case where r = n − 1.

12) A complete bipartite graph Kₘ,ₙ has:

M × n edges

(m + n)(m − 1)/2 edges

M + n edges

M × (n − 1) edges

A complete bipartite graph Kₘ,ₙ contains m × n edges because every one of the m vertices in the first partition connects to each of the n vertices in the second partition, creating exactly one edge for each such pair and therefore producing a total equal to the product m times n.

Explanation

A complete bipartite graph Kₘ,ₙ contains m × n edges because every one of the m vertices in the first partition connects to each of the n vertices in the second partition, creating exactly one edge for each such pair and therefore producing a total equal to the product m times n.

13) Which statements about weighted graphs are true?

Each edge carries a numerical value called weight.

Weights may represent cost, distance, or capacity.

Weighted graphs cannot be directed.

Weights influence the computation of shortest paths.

Weighted graphs have the property that each edge carries a numerical value called a weight that may represent cost, distance, time, reliability, or capacity, and these weights can occur in either directed or undirected graphs, so weighted graphs are not restricted to one orientation, and classical algorithms such as Dijkstra’s, Bellman–Ford, Prim’s, and Kruskal’s all rely on these weights to compute shortest paths or minimum spanning structures.

Explanation

Weighted graphs have the property that each edge carries a numerical value called a weight that may represent cost, distance, time, reliability, or capacity, and these weights can occur in either directed or undirected graphs, so weighted graphs are not restricted to one orientation, and classical algorithms such as Dijkstra’s, Bellman–Ford, Prim’s, and Kruskal’s all rely on these weights to compute shortest paths or minimum spanning structures.

Submit

14) A bipartite graph is one in which:

Vertices can be divided into two disjoint sets so that every edge joins vertices from different sets

Vertices form two groups where edges may connect vertices within a group

Graph has exactly two components

All vertices have degree 2

Bipartite means vertices can be split into two sets V₁ and V₂ such that each edge connects a vertex in V₁ to one in V₂.

Mathematically: V = V₁ ∪ V₂ with V₁ ∩ V₂ = ∅ and ∀(u,v)∈E, u∈V₁ ⇒ v∈V₂.

A gives the definition: vertices split into two disjoint sets with edges only between the sets.

C gives the key property: a graph is bipartite if and only if it has no odd cycles.

B is false — edges within a group break bipartiteness.

D is false — vertex degree isn’t relevant.

Explanation

Bipartite means vertices can be split into two sets V₁ and V₂ such that each edge connects a vertex in V₁ to one in V₂.

Mathematically: V = V₁ ∪ V₂ with V₁ ∩ V₂ = ∅ and ∀(u,v)∈E, u∈V₁ ⇒ v∈V₂.

A gives the definition: vertices split into two disjoint sets with edges only between the sets.

C gives the key property: a graph is bipartite if and only if it has no odd cycles.

B is false — edges within a group break bipartiteness.

D is false — vertex degree isn’t relevant.

Submit

15) A directed edge from u to v is denoted how?

[u, v]

{u, v}

(u, v)

U - v

The ordered pair (u,v) places the tail vertex u first and the head vertex v second, indicating direction. Curly braces {u,v} denote unordered pairs used for undirected edges. Square brackets [u,v] are not standard edge notation. The hyphen notation u-v is informal and does not encode direction.

Explanation

The ordered pair (u,v) places the tail vertex u first and the head vertex v second, indicating direction. Curly braces {u,v} denote unordered pairs used for undirected edges. Square brackets [u,v] are not standard edge notation. The hyphen notation u-v is informal and does not encode direction.

16) A graph where each pair of distinct vertices is connected by exactly one edge is called what?

Bipartite graph

Complete graph

Regular graph

Planar graph

A complete graph Kn connects every distinct pair of vertices with exactly one edge, giving n(n-1)/2 total edges. A bipartite graph only connects vertices between two partitions. A regular graph has uniform vertex degrees but need not connect all pairs. A planar graph is a drawing property unrelated to completeness.

Explanation

A complete graph Kn connects every distinct pair of vertices with exactly one edge, giving n(n-1)/2 total edges. A bipartite graph only connects vertices between two partitions. A regular graph has uniform vertex degrees but need not connect all pairs. A planar graph is a drawing property unrelated to completeness.

17) In a weighted graph, the total cost of a path equals what operation applied to its edge weights?

Sum

Product

Maximum

Average

The cost of a path is the sum of the weights of all its edges. Shortest-path algorithms such as Dijkstra's and Bellman-Ford compare paths by their cumulative weight sums to identify the minimum cost route. Option A would produce unreasonably large values. Options B and D do not correctly measure traversal cost.

Explanation

The cost of a path is the sum of the weights of all its edges. Shortest-path algorithms such as Dijkstra's and Bellman-Ford compare paths by their cumulative weight sums to identify the minimum cost route. Option A would produce unreasonably large values. Options B and D do not correctly measure traversal cost.

18) A vertex whose removal increases the number of connected components is called what?

Pendant vertex

Bridge vertex

Articulation vertex

Isolated vertex

An articulation point, also called a cut vertex, is critical for connectivity. Removing it along with its incident edges disconnects the graph, increasing the component count. A pendant vertex has degree 1 and its removal may not disconnect the graph. A bridge is an edge not a vertex. An isolated vertex has degree 0 and no incident edges to remove.

Explanation

An articulation point, also called a cut vertex, is critical for connectivity. Removing it along with its incident edges disconnects the graph, increasing the component count. A pendant vertex has degree 1 and its removal may not disconnect the graph. A bridge is an edge not a vertex. An isolated vertex has degree 0 and no incident edges to remove.

19) The complement of an empty graph with n vertices is what?

A complete graph Kn

A path graph

A cycle graph

A bipartite graph

An empty graph contains no edges. Its complement includes all edges absent from the original, which is every possible edge between the n vertices, producing the complete graph Kn with all n(n-1)/2 edges. Options A, B, and D are specific graph structures that only coincide with Kn under very special conditions.

Explanation

An empty graph contains no edges. Its complement includes all edges absent from the original, which is every possible edge between the n vertices, producing the complete graph Kn with all n(n-1)/2 edges. Options A, B, and D are specific graph structures that only coincide with Kn under very special conditions.

20) A connected graph with no cycles and n vertices always has how many edges?

N

N + 1

N - 1

N - 2

A tree has exactly n-1 edges, giving minimal connectivity with no redundant paths. Adding any edge creates a cycle and removing any edge disconnects the graph. Option A gives n edges which guarantees at least one cycle. Option B gives n+1 which produces even more cycles. Option D gives n-2 which is insufficient to keep all vertices connected.

Explanation

A tree has exactly n-1 edges, giving minimal connectivity with no redundant paths. Adding any edge creates a cycle and removing any edge disconnects the graph. Option A gives n edges which guarantees at least one cycle. Option B gives n+1 which produces even more cycles. Option D gives n-2 which is insufficient to keep all vertices connected.