Fundamentals Of Graph Terminology

1) A graph consists of two finite sets: one of ____ and one of ____.

Vertices; Edges

Edges; Paths

Lines; Angles

Circles; Centers

A graph consists of two finite sets—one of vertices and one of edges—because a graph G = (V, E) is defined by its vertex set V, which contains the points or nodes, and its edge set E, which contains the connections between pairs of vertices, making “vertices; edges” the only pair that matches the formal definition.

Explanation

A graph consists of two finite sets—one of vertices and one of edges—because a graph G = (V, E) is defined by its vertex set V, which contains the points or nodes, and its edge set E, which contains the connections between pairs of vertices, making “vertices; edges” the only pair that matches the formal definition.

2) Which of these graphs has no loops and no multiple edges between vertices?

Multigraph

Simple graph

Pseudograph

Weighted graph

A simple graph is the one with no loops and no multiple edges because simplicity prohibits any edge that begins and ends at the same vertex and also prohibits multiple parallel edges between the same two vertices, whereas multigraphs allow parallel edges and pseudographs allow loops, so only a simple graph fits both restrictions simultaneously.

Explanation

A simple graph is the one with no loops and no multiple edges because simplicity prohibits any edge that begins and ends at the same vertex and also prohibits multiple parallel edges between the same two vertices, whereas multigraphs allow parallel edges and pseudographs allow loops, so only a simple graph fits both restrictions simultaneously.

3) In an undirected graph, each edge connects:

A vertex to itself

An ordered pair of vertices

An unordered pair of vertices

No vertices

In an undirected graph each edge connects an unordered pair of vertices because the lack of direction means the pair {u, v} is identical to {v, u}, unlike directed graphs which use ordered pairs (u, v), and therefore the correct description is that edges connect unordered vertex pairs.

Explanation

In an undirected graph each edge connects an unordered pair of vertices because the lack of direction means the pair {u, v} is identical to {v, u}, unlike directed graphs which use ordered pairs (u, v), and therefore the correct description is that edges connect unordered vertex pairs.

4) The degree of a vertex is:

Number of vertices in the graph

Number of edges incident to it

Total number of loops in graph

The length of its label

The degree of a vertex is the number of edges incident to it because each edge touching that vertex contributes to its degree, and in undirected graphs a loop contributes 2 since it touches the vertex twice, making degree a measure of edge incidence rather than label length, total vertices, or loop count.

Explanation

The degree of a vertex is the number of edges incident to it because each edge touching that vertex contributes to its degree, and in undirected graphs a loop contributes 2 since it touches the vertex twice, making degree a measure of edge incidence rather than label length, total vertices, or loop count.

5) If a graph has 5 vertices and 10 edges where every vertex is connected to every other, what type is it?

Bipartite

Regular

Complete

Disconnected

A graph with 5 vertices in which every vertex is connected to every other vertex and which has 10 edges must be a complete graph because a complete graph Kₙ contains exactly n(n−1)/2 edges, and substituting n = 5 gives 5·4/2 = 10, showing that all possible connections are present.

Explanation

A graph with 5 vertices in which every vertex is connected to every other vertex and which has 10 edges must be a complete graph because a complete graph Kₙ contains exactly n(n−1)/2 edges, and substituting n = 5 gives 5·4/2 = 10, showing that all possible connections are present.

6) Identify the incorrect statement.

A graph with one vertex and no edge is connected.

A disconnected graph can have isolated vertices.

A connected graph has exactly one component.

A tree contains at least one cycle.

The incorrect statement is “A tree contains at least one cycle” because a tree is defined as a connected acyclic graph, meaning it has exactly one component and no cycles at all, whereas the other statements correctly describe that a one-vertex graph with no edges is connected, a disconnected graph can have isolated vertices, and a connected graph has exactly one component.

Explanation

The incorrect statement is “A tree contains at least one cycle” because a tree is defined as a connected acyclic graph, meaning it has exactly one component and no cycles at all, whereas the other statements correctly describe that a one-vertex graph with no edges is connected, a disconnected graph can have isolated vertices, and a connected graph has exactly one component.

7) The sum of degrees of all vertices equals:

Number of vertices

Twice the number of edges

Number of components

Number of loops

The sum of degrees of all vertices equals twice the number of edges because each undirected edge contributes 1 to the degree of each of its two endpoints, giving a total contribution of 2 per edge, which is the essence of the Handshaking Lemma: Σ deg(v) = 2|E|.

Explanation

The sum of degrees of all vertices equals twice the number of edges because each undirected edge contributes 1 to the degree of each of its two endpoints, giving a total contribution of 2 per edge, which is the essence of the Handshaking Lemma: Σ deg(v) = 2|E|.

8) Which pair correctly matches the term and its meaning?

Path — a sequence of vertices where edges may repeat

Trail — a sequence of edges where vertices may repeat

Circuit — a closed path where no edge repeats

Cycle — a path where repetition of edges is allowed

The correct match is “Circuit — a closed path where no edge repeats” because a circuit starts and ends at the same vertex while forbidding repeated edges, a trail allows repeated vertices but not repeated edges, a path forbids repeated vertices, and a cycle is a closed path that repeats only its starting vertex, so the only accurate pairing given is the one describing a circuit.

Explanation

The correct match is “Circuit — a closed path where no edge repeats” because a circuit starts and ends at the same vertex while forbidding repeated edges, a trail allows repeated vertices but not repeated edges, a path forbids repeated vertices, and a cycle is a closed path that repeats only its starting vertex, so the only accurate pairing given is the one describing a circuit.

9) A simple graph cannot contain a loop.

True

False

A simple graph cannot contain a loop, which is true, because a loop is an edge that connects a vertex to itself and simple graphs explicitly forbid both loops and multiple edges, meaning that the presence of a loop would violate the simplicity condition.

Explanation

A simple graph cannot contain a loop, which is true, because a loop is an edge that connects a vertex to itself and simple graphs explicitly forbid both loops and multiple edges, meaning that the presence of a loop would violate the simplicity condition.

10) The degree of every vertex in K4 is 3.

True

False

The degree of every vertex in K₄ is 3, which is true, because in a complete graph every vertex connects to all other n−1 vertices, so in K₄ each vertex is adjacent to 3 others, giving each vertex degree 3.

Explanation

The degree of every vertex in K₄ is 3, which is true, because in a complete graph every vertex connects to all other n−1 vertices, so in K₄ each vertex is adjacent to 3 others, giving each vertex degree 3.

11) A graph with one isolated vertex and one edge is connected.

True

False

A graph with one isolated vertex and one edge is not connected, making the statement false, because the isolated vertex forms a separate component from the vertices joined by the edge, resulting in at least two components and therefore disconnectivity.

Explanation

A graph with one isolated vertex and one edge is not connected, making the statement false, because the isolated vertex forms a separate component from the vertices joined by the edge, resulting in at least two components and therefore disconnectivity.

12) A tree with n vertices always has n edges.

True

False

The statement “A tree with n vertices always has n edges” is false because a tree with n vertices has exactly n−1 edges, which is a defining property that ensures the graph stays connected while avoiding cycles.

Explanation

The statement “A tree with n vertices always has n edges” is false because a tree with n vertices has exactly n−1 edges, which is a defining property that ensures the graph stays connected while avoiding cycles.

13) Every connected graph with n vertices and n − 1 edges is a tree.

True

False

Every connected graph with n vertices and n−1 edges is a tree, which is true, because having exactly n−1 edges in a connected graph guarantees no cycles and minimal connectivity, making the graph both connected and acyclic, the two conditions required for a tree.

Explanation

Every connected graph with n vertices and n−1 edges is a tree, which is true, because having exactly n−1 edges in a connected graph guarantees no cycles and minimal connectivity, making the graph both connected and acyclic, the two conditions required for a tree.

14) In an undirected simple graph, a vertex of degree 0 is isolated.

True

False

In an undirected simple graph, a vertex of degree 0 is isolated, which is true, because degree 0 means the vertex has no incident edges and therefore no adjacency to any other vertex, placing it in a component by itself.

Explanation

In an undirected simple graph, a vertex of degree 0 is isolated, which is true, because degree 0 means the vertex has no incident edges and therefore no adjacency to any other vertex, placing it in a component by itself.

15) A graph G = (V, E) is defined by a set of ____ and a set of ____.

A graph G = (V, E) is defined by a set of vertices and a set of edges because the ordered pair (V, E) captures both the objects of the graph (vertices) and the relationships between them (edges), forming the complete structure.

Explanation

A graph G = (V, E) is defined by a set of vertices and a set of edges because the ordered pair (V, E) captures both the objects of the graph (vertices) and the relationships between them (edges), forming the complete structure.

Submit

16) The number of edges in a complete graph Kₙ is ____.

The number of edges in a complete graph Kₙ is n(n−1)/2 because each of the n vertices connects to n−1 others, giving n(n−1) ordered pairs, and dividing by 2 removes the duplication caused by unordered edges in undirected graphs.

Explanation

The number of edges in a complete graph Kₙ is n(n−1)/2 because each of the n vertices connects to n−1 others, giving n(n−1) ordered pairs, and dividing by 2 removes the duplication caused by unordered edges in undirected graphs.

Submit

17) A vertex with no incident edges is called an ____ vertex.

A vertex with no incident edges is called an isolated vertex because having degree 0 means it shares no connection with the rest of the graph, effectively forming its own trivial component.

Explanation

A vertex with no incident edges is called an isolated vertex because having degree 0 means it shares no connection with the rest of the graph, effectively forming its own trivial component.

Submit

18) A graph that can be drawn without edges crossing is called ____.

A graph that can be drawn without any edges crossing is called planar because planarity refers to the ability to embed the graph in the plane such that all edges appear as non-intersecting curves, which is fundamental to planar graph theory and Kuratowski’s theorem.

Explanation

A graph that can be drawn without any edges crossing is called planar because planarity refers to the ability to embed the graph in the plane such that all edges appear as non-intersecting curves, which is fundamental to planar graph theory and Kuratowski’s theorem.

Submit

19) A simple closed path that visits no vertex twice (except start = end) is a ____.

A simple closed path that visits no vertex twice (except for the required return to the start) is a cycle because a cycle is defined as a closed path with no repetition of vertices or edges other than the starting/ending vertex, forming a minimal loop.

Explanation

A simple closed path that visits no vertex twice (except for the required return to the start) is a cycle because a cycle is defined as a closed path with no repetition of vertices or edges other than the starting/ending vertex, forming a minimal loop.

Submit

20) The number of edges equals half the sum of vertex ____.

The number of edges equals half the sum of vertex degrees because Σ deg(v) counts each edge twice—once at each endpoint—so dividing by two yields |E| = ½ Σ deg(v), which is exactly the statement of the Handshaking Lemma.

Explanation

The number of edges equals half the sum of vertex degrees because Σ deg(v) counts each edge twice—once at each endpoint—so dividing by two yields |E| = ½ Σ deg(v), which is exactly the statement of the Handshaking Lemma.

Submit

Fundamentals of Graph Terminology