#graph #degreeofgraph

Question

Every simple, undirected, connected and acyclic graph with 50 vertices has at least two vertices of degree one.

Answer 1

Proof by Contradiction

Assume the opposite: a simple, undirected, connected, and acyclic graph exists with 50 vertices where all vertices have a degree greater than one, i.e., no vertices have a degree of one.

Since the graph is connected and acyclic, it must be a tree, as trees are acyclic-connected graphs. Now, let's consider the properties of trees:

• A tree with $n$ vertices has exactly $n-1$ edges.
• A tree must have at least two vertices with a degree of one (leaf nodes).

Now, since our assumption states that all vertices have a degree greater than one, it contradicts the fact that a tree must have at least two vertices with a degree of one. Therefore, our assumption that a simple, undirected, connected, and acyclic graph exists with 50 vertices where all vertices have a degree greater than one is false.

Hence, by contradiction, we can conclude that every simple, undirected, connected, and acyclic graph with 50 vertices must have at least two vertices with a degree of one.

Answer 2

Any Graph which is connected and acyclic is nothing but a Tree. In any Tree, there will be n-1 edges with n vertices. By the total Degree Theorem Total degree should be 2(n-1).

__________________________________________________________________________________

Use Proof by Contradiction technique:

Let's Take 1 node with degree 1 and all n-1 nodes with a degree more than 1, so the total degree will be >=2(n-1)+1 which is >=2n-1

So by definition, it is not a Tree it should have a 2n-2 total degrees. Hence every tree should have at least two vertices of degree one.