Advanced Graph Terminology

1) 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.

2) 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.

3) 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

4) 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

5) 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.

6) 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.

7) 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.

8) 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.

9) 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.

10) 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.

11) 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.

12) 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.

13) 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.

14) 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.

15) A directed edge from vertex u to v is denoted as _____.

A directed edge from vertex u to vertex v is written as (u, v) because the ordered pair notation indicates direction by placing the tail vertex first and the head vertex second, distinguishing it clearly from undirected edges which are written with unordered braces {u, v}.

Explanation

A directed edge from vertex u to vertex v is written as (u, v) because the ordered pair notation indicates direction by placing the tail vertex first and the head vertex second, distinguishing it clearly from undirected edges which are written with unordered braces {u, v}.

Submit

16) A graph where each pair of vertices is connected by exactly one edge is called a _____.

A complete graph Kₙ contains every possible edge between its n vertices because each vertex connects to all n − 1 other vertices, giving n(n − 1) total ordered connections, but since an undirected edge does not distinguish between (u, v) and (v, u), each edge is counted twice in that total, so dividing by 2 gives the exact number of unique edges: n(n − 1)/2.

Explanation

A complete graph Kₙ contains every possible edge between its n vertices because each vertex connects to all n − 1 other vertices, giving n(n − 1) total ordered connections, but since an undirected edge does not distinguish between (u, v) and (v, u), each edge is counted twice in that total, so dividing by 2 gives the exact number of unique edges: n(n − 1)/2.

Submit

17) In a weighted graph, the total cost of a path equals the _____ of the weights of its edges.

The cost of a path is computed by summing the weights of all edges along that path, so if the path consists of edges e₁, e₂, …, eₖ with corresponding weights w(e₁), w(e₂), …, w(eₖ), then its total cost is w(e₁) + w(e₂) + … + w(eₖ), and this cumulative value is what shortest-path algorithms such as Dijkstra’s, Bellman–Ford, and A evaluate in order to compare different routes and choose the one with the minimum total weight.

Explanation

The cost of a path is computed by summing the weights of all edges along that path, so if the path consists of edges e₁, e₂, …, eₖ with corresponding weights w(e₁), w(e₂), …, w(eₖ), then its total cost is w(e₁) + w(e₂) + … + w(eₖ), and this cumulative value is what shortest-path algorithms such as Dijkstra’s, Bellman–Ford, and A evaluate in order to compare different routes and choose the one with the minimum total weight.

Submit

18) A vertex whose removal increases the number of connected components is an _____ vertex.

A vertex whose removal disconnects the graph is called an articulation point—also known as a cut vertex—because it is critical for maintaining connectivity, and deleting it (along with its incident edges) increases the number of connected components, indicating that the structure of the graph depends on that vertex to hold major parts of the network together.

Explanation

A vertex whose removal disconnects the graph is called an articulation point—also known as a cut vertex—because it is critical for maintaining connectivity, and deleting it (along with its incident edges) increases the number of connected components, indicating that the structure of the graph depends on that vertex to hold major parts of the network together.

Submit

19) The complement of an empty graph with n vertices is _____.

Because the empty graph on n vertices contains no edges at all, its complement—which includes precisely those edges missing from the original—must contain every possible edge between the n vertices, meaning it forms the complete graph Kₙ with all n(n − 1)/2 undirected edges present.

Explanation

Because the empty graph on n vertices contains no edges at all, its complement—which includes precisely those edges missing from the original—must contain every possible edge between the n vertices, meaning it forms the complete graph Kₙ with all n(n − 1)/2 undirected edges present.

Submit

20) A connected graph with no cycles and n vertices always has _____ edges.

A tree has exactly one fewer edge than vertices, meaning |E| = |V| − 1, and this guarantees minimal connectivity because the graph remains connected with just enough edges to link all vertices while avoiding cycles, since adding any extra edge would create a cycle and removing any existing edge would disconnect the graph.

Explanation

A tree has exactly one fewer edge than vertices, meaning |E| = |V| − 1, and this guarantees minimal connectivity because the graph remains connected with just enough edges to link all vertices while avoiding cycles, since adding any extra edge would create a cycle and removing any existing edge would disconnect the graph.

Submit