Let G be a simple connected graph with n nodes and N edges, and there are nodes with degree 3 in G. it is proved that there is at least one node with degree 1 in G

Let G be a simple connected graph with n nodes and N edges, and there are nodes with degree 3 in G. it is proved that there is at least one node with degree 1 in G

Let G be a connected graph, so the degree of G is at least 2
G has nodes of degree 3, so the sum of degrees of all nodes of G is greater than or equal to 2 (n-1) + 3 = 2n + 1
And G has n sides, and the sum of degrees is 2n
Contradiction
So there is at least one node with degree 1 in G

Elden Ring Premiere

RELATED INFORMATIONS