Degree Of A Vertex (Conceptual Foundations)

1) The degree of a vertex in an undirected graph is:

The number of edges in the entire graph

The number of edges incident to that vertex

The number of vertices adjacent to it divided by 2

The number of loops in the whole graph

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.

Explanation

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.

2) In a graph with vertices A, B, C, D, and edges AB, AC, AD, what is deg(A)?

1

2

3

4

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.

Explanation

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.

3) Which identity always holds for an undirected graph?

∑ deg(v) = |V|

∑ deg(v) = 2|E|

∑ deg(v) = |E| / |V|

∑ deg(v) = |E| + |V|

"Every edge connects two vertices, adding 1 to each endpoint’s degree. Therefore, all edges together contribute 2 to the total sum of degrees: ∑deg(v)=2∣E∣. This rule is known as the Handshaking Lemma.

Explanation

"Every edge connects two vertices, adding 1 to each endpoint’s degree. Therefore, all edges together contribute 2 to the total sum of degrees: ∑deg(v)=2∣E∣. This rule is known as the Handshaking Lemma.

4) A graph has 5 vertices with degrees 2,2,3,3,2. How many edges does the graph have?

5

6

7

8

Add all degrees: 2 + 2 + 3 + 3 + 2 = 12.

By the Handshaking Lemma, edges = (∑ deg v) / 2 = 12 / 2 = 6.

Dividing by 2 avoids double-counting each edge’s two endpoints.

Explanation

Add all degrees: 2 + 2 + 3 + 3 + 2 = 12.

By the Handshaking Lemma, edges = (∑ deg v) / 2 = 12 / 2 = 6.

Dividing by 2 avoids double-counting each edge’s two endpoints.

5) Which description fits a vertex of degree 0?

A vertex with a loop

An isolated vertex

A vertex connected to all others

A vertex appearing in every cycle

Degree 0 means no incident edges. Such a vertex stands completely alone, forming its own component. In diagrams, it appears as a point with no connecting lines.

Explanation

Degree 0 means no incident edges. Such a vertex stands completely alone, forming its own component. In diagrams, it appears as a point with no connecting lines.

6) A vertex has one loop and two other distinct edges attached. What is its degree?

2

3

4

5

Loop → 2 contributions, plus 2 more edges → 2 + 2 = 4.

Always remember:

Ordinary edge = 1 to the vertex.

Loop = 2 to the vertex it touches.

Explanation

Loop → 2 contributions, plus 2 more edges → 2 + 2 = 4.

Always remember:

Ordinary edge = 1 to the vertex.

Loop = 2 to the vertex it touches.

7) If every vertex in a 6-vertex graph has degree 5, the graph is:

Regular

Bipartite

Tree

Disconnected

Each vertex has the same degree r = 5, so it’s a 5-regular graph.

For n = 6, r = n − 1 means every vertex connects to all others—this is actually the complete graph K₆.

Explanation

Each vertex has the same degree r = 5, so it’s a 5-regular graph.

For n = 6, r = n − 1 means every vertex connects to all others—this is actually the complete graph K₆.

8) Which statement about vertex degrees is always true?

The number of vertices of odd degree is even

There are equal numbers of even and odd degree vertices

Exactly one vertex can have an odd degree

The sum of degrees is odd

Because ∑ deg(v) = 2|E| is even, the total number of odd addends in that sum must be even. Hence, vertices of odd degree always come in pairs (0, 2, 4, …).

Explanation

Because ∑ deg(v) = 2|E| is even, the total number of odd addends in that sum must be even. Hence, vertices of odd degree always come in pairs (0, 2, 4, …).

9) In a simple graph with n vertices, the largest possible degree of any vertex is n − 1.

True

False

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.

Explanation

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.

10) In any graph, at least one vertex must have an odd degree.

True

False

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.

Explanation

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.

11) A loop adds 1 to the degree of its vertex.

True

False

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.

Explanation

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.

12) Two graphs with the same degree sequence must be identical.

True

False

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.

Explanation

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.

13) In any tree with at least two vertices, at least two vertices have degree 1.

True

False

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.

Explanation

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.

14) A vertex of degree n − 1 in an n-vertex graph is adjacent to every other vertex.

True

False

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.

Explanation

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.

15) The degree of vertex v is the number of ____ incident to v.

The degree of a vertex v is the number of edges incident to v because deg(v) is defined by counting all edges that touch v, and in undirected graphs any loop touching v is counted twice since it contributes two incidences at that vertex.

Explanation

The degree of a vertex v is the number of edges incident to v because deg(v) is defined by counting all edges that touch v, and in undirected graphs any loop touching v is counted twice since it contributes two incidences at that vertex.

Submit

16) In any simple graph, ∑ deg(v) = ____.

In any simple graph the sum of all vertex degrees ∑ deg(v) equals 2|E| because each edge contributes 1 to the degree of each of its two endpoints, so when you add all degrees you count every edge exactly twice, once from each side.

Explanation

In any simple graph the sum of all vertex degrees ∑ deg(v) equals 2|E| because each edge contributes 1 to the degree of each of its two endpoints, so when you add all degrees you count every edge exactly twice, once from each side.

Submit

17) A vertex connected to every other vertex has degree ____.

A vertex connected to every other vertex in an n-vertex graph has degree n − 1 because it must have one edge to each of the remaining n − 1 vertices and no edge to itself in a simple graph, giving a total of n − 1 incident edges.

Explanation

A vertex connected to every other vertex in an n-vertex graph has degree n − 1 because it must have one edge to each of the remaining n − 1 vertices and no edge to itself in a simple graph, giving a total of n − 1 incident edges.

Submit

18) The vertices of degree 1 in a tree are called ____ vertices.

The vertices of degree 1 in a tree are called leaf (or end) vertices because each such vertex lies at the extremity of the tree with exactly one connecting edge, and removing a leaf along with its incident edge reduces both the vertex and edge counts by 1 while keeping the graph a smaller tree that remains connected and acyclic.

Explanation

The vertices of degree 1 in a tree are called leaf (or end) vertices because each such vertex lies at the extremity of the tree with exactly one connecting edge, and removing a leaf along with its incident edge reduces both the vertex and edge counts by 1 while keeping the graph a smaller tree that remains connected and acyclic.

Submit

19) In any undirected graph, the sum of all vertex degrees is always an ____ number.

In any undirected graph the sum of all vertex degrees is always an even number because by the Handshaking Lemma it equals 2|E|, and since 2 times any integer number of edges |E| is even, the total degree sum cannot be odd.

Explanation

In any undirected graph the sum of all vertex degrees is always an even number because by the Handshaking Lemma it equals 2|E|, and since 2 times any integer number of edges |E| is even, the total degree sum cannot be odd.

Submit

20) The Handshaking Lemma states that ∑ deg(v) = ____ × number of edges.

The Handshaking Lemma states that ∑ deg(v) = 2 × number of edges because every undirected edge contributes 1 to the degree of each of its two endpoints, so when we sum the degrees across all vertices we effectively count each edge exactly twice, producing the factor of 2.

Explanation

The Handshaking Lemma states that ∑ deg(v) = 2 × number of edges because every undirected edge contributes 1 to the degree of each of its two endpoints, so when we sum the degrees across all vertices we effectively count each edge exactly twice, producing the factor of 2.

Submit

Degree of a Vertex (Conceptual Foundations)