Degree of a Vertex (Conceptual Foundations)

The statement is false because in degree counting for undirected graphs a loop at a vertex v is considered to touch v twice—once as it “leaves” and once as it “arrives” back—so a single loop contributes 2 to deg(v), not 1.

Each undirected edge has two endpoints and contributes 1 to the degree of each, so it is counted twice in the degree sum. Summing over all vertices counts every edge exactly twice, giving the factor of 2. Options 1, 3, and 4 do not correctly account for the double-counting of each edge's two endpoints.

By the Handshaking Lemma the degree sum equals 2 times the number of edges. Since 2 multiplied by any integer is even, the total degree sum is always even regardless of the graph's structure. An odd degree sum would contradict the lemma and indicate a counting error.

Degree-1 vertices in a tree are called leaves because they lie at the extremities with exactly one connecting edge. Removing a leaf and its edge produces a smaller valid tree. Root is the designated starting vertex. Branch vertices have degree greater than 1. Hub is an informal term not used in standard graph theory.

A vertex connected to every other vertex has one edge to each of the remaining n-1 vertices. In a simple graph there are no loops so no edge to itself. The degree is exactly n-1. Option A would require an edge to itself. Option B exceeds the maximum possible degree. Option D is one short of the full connection.

Each edge contributes 1 to the degree of each of its two endpoints, so summing all degrees counts every edge exactly twice. The result is 2 times the number of edges, which is the Handshaking Lemma. The other options have no derivation from the structure of edges and vertices.

Since the degree sum equals 2 times the number of edges, it is always even. For an even sum, the number of odd addends must be even. Therefore vertices of odd degree always come in pairs, giving a count of 0, 2, 4, and so on. Options B, C, and D all contradict the Handshaking Lemma.

The statement is true because in an n-vertex graph a vertex of degree n − 1 must have an edge connecting it to each of the other n − 1 vertices, which makes it adjacent to all of them and thus a universal vertex.

The statement is true because in any tree with at least two vertices there must be at least two vertices of degree 1, called leaves, which occur at the ends of any longest path in the tree, and if there were fewer than two such leaves the structure would either not be connected or would contain a cycle, contradicting the definition of a tree, while the special one-vertex tree has degree 0 and simply acts as an edge case.

The statement is false because two graphs can share the same degree sequence, meaning each graph has vertices with the same degrees when sorted, but still differ in how those vertices are connected, so they need not be isomorphic or structurally identical even if their degree sequences match.

Each edge touching a vertex contributes 1 to its degree because it forms a connection to another vertex. If the vertex has a loop (an edge connecting back to itself), that loop touches the vertex twice, so it contributes 2.

The statement is false because although some graphs must have vertices of odd degree, it is entirely possible for every vertex in a graph to have even degree, as shown by a 4-cycle C₄ where each of the 4 vertices has degree 2, giving an example with no odd-degree vertices.

The statement is true because in a simple graph with n vertices loops are not allowed, so a vertex cannot connect to itself and the most edges it can have is one to each of the other n − 1 vertices, making n − 1 the largest possible degree.

Vertex A is incident to three edges (AB, AC, AD). No loops or repeated edges exist, so deg(A) = 3. Always count how many edges directly meet the vertex, not how many other vertices exist in total.