Question

Show that every graph with two or more nodes contains two nodes that have equal degrees.

Short answer

It can be shown that every graph with two or more nodes contains two nodes that have equal degrees.

Step-by-step solution

Explain graph

Graph is the pictorial representation that is the combinations of nodes and edges.Degree is the total number of edges a node is connected.

Show that every graph with two or more nodes contains two nodes that have equal degrees.

Consider a graph$G$ which has at least one edge, without having any loops or cycles. In graph$G$ , prove that there are at least two nodes with degree 1.

In a graph $G$, consider the node $V_1$at which only one edge $E_1$is incident.

$\mathrm{deg}\left(V_1\right)=1$

Consider that the other end of the $E_1$is at $V_2$. If there exists no other edges which is incident at $V_2$.

$\mathrm{deg}\left(V_2\right)=1$

Let$E_2$ be the edge which is incident at $V_2$. Proceeding like this, node$V_k$ will be obtained that has the degree value 1 and it is equal to the degree of$V_1$ node.

Thus, the graph$G$ has at least two nodes of degree 1.

Therefore, it has been proved that every graph with two or more nodes contains two nodes that have equal degrees.