Fundamentals of Graph Terminology

A tree is defined as a connected acyclic graph — it has no cycles whatsoever. Options A, B, and C are all correct: a single-vertex graph with no edges is trivially connected, disconnected graphs can have isolated vertices, and a connected graph by definition has exactly one component.

The Handshaking Lemma states that the sum of all vertex degrees equals twice the number of edges. Each edge contributes 1 to the degree of each endpoint, so it is counted twice in the degree sum. Dividing by 2 recovers the edge count. Weights, labels, and components have no direct role in this identity.

A cycle is a closed path that returns to its starting vertex without repeating any other vertex or any edge. A walk allows repetition of both vertices and edges. A trail allows repeated vertices but not edges. A path allows no repetition of vertices or edges but need not be closed. Only a cycle is both closed and non-repeating.

A planar graph can be embedded in the plane with no edge crossings. Options A and B describe properties of paths and cycles within graphs rather than drawing properties. Option D describes a graph whose vertices can be divided into two independent sets, which is unrelated to whether edges cross.

An isolated vertex has degree 0 — no edges touch it and it has no neighbors. It forms its own trivial component. Option A describes a pendant vertex which has degree exactly 1. Option C describes the relationship between two connected vertices. Option D names a specific degree value, not a classification for degree-0 vertices.

Each of the n vertices connects to n-1 others, giving n(n-1) ordered pairs. Dividing by 2 removes duplication since each undirected edge is counted from both endpoints. Option A omits the n-1 factor. Option B uses n+1 instead of n-1. Option D uses n squared, overcounting by including self-connections.

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. A cycle is a closed path repeating only the starting vertex. Only option C correctly describes its named concept.

The ordered pair (V, E) captures the two fundamental components of any graph: V is the vertex set containing the nodes and E is the edge set containing the connections between pairs of vertices. Options A, C, and D mix unrelated or partial concepts that do not form the complete formal definition.

Each undirected edge contributes 1 to the degree of each of its two endpoints, giving a total contribution of 2 per edge. Summing over all vertices therefore counts each edge twice, giving the Handshaking Lemma: sum of degrees = 2 times the number of edges. Options A, C, and D have no direct relationship to the degree sum.

The answer is True. Degree 0 means no edges are incident to the vertex. With no connections to any other vertex it forms a component by itself. An isolated vertex has no neighbors and does not contribute to any path in the graph.

A graph G = (V, E) is defined by its vertex set V containing the nodes and its edge set E containing connections between pairs of vertices. Option B names edges twice in different forms. Options C and D name geometric objects unrelated to graph theory.

The answer is True. Having exactly n-1 edges in a connected graph guarantees no cycles and minimal connectivity. Any fewer edges would disconnect the graph and any more would create a cycle. This combination of connectivity and acyclicity is precisely the definition of a tree.

A complete graph Kn has n(n-1)/2 edges. With n=5: 5 times 4 divided by 2 = 10. Every possible connection between distinct vertices is present. Option A incorrectly labels it bipartite. Option B gives the wrong count and wrong label. Option D contradicts the definition since all vertices are connected.

The answer is False. A tree with n vertices has exactly n-1 edges. This is a defining property ensuring the graph remains connected while containing no cycles. Adding one more edge to a tree always creates exactly one cycle.

The degree of a vertex counts the edges touching it. Each edge contributes 1 to the degree of each endpoint, and a loop contributes 2 since it touches the same vertex twice. Option A counts global vertices not local incidence. Options C and D have no standard relationship to degree.

The answer is False. The isolated vertex forms its own component separate from the two vertices joined by the edge. With at least two components the graph is disconnected. A connected graph requires every pair of vertices to be joined by a path, which is impossible here since the isolated vertex has no edges.

In an undirected graph the edge between u and v is the same as the edge between v and u, so the pair is unordered. Directed graphs use ordered pairs to indicate direction. Option A describes a loop. Option D describes an isolated edge with no endpoints, which is not a valid graph element.

The answer is True. In a complete graph every vertex connects to all other n-1 vertices. In K4 each vertex is adjacent to the other 3 vertices, giving each vertex degree 3. The total degree sum is 4 times 3 = 12 = 2 times 6 edges, which is consistent with the Handshaking Lemma.

A simple graph prohibits any edge beginning and ending at the same vertex and also prohibits parallel edges between the same two vertices. Multigraphs allow parallel edges, pseudographs allow loops, and weighted graphs assign values to edges but have no restrictions on loops or multiples. Only a simple graph enforces both restrictions simultaneously.

The answer is True. A simple graph explicitly forbids both loops and multiple edges. A loop is an edge connecting a vertex to itself, which violates the simplicity condition. Any graph containing a loop is at minimum a pseudograph, not a simple graph.