Question

Let G be a graph on n vertices. Prove the following:
a) δ(G) + δ(G') < n-1

Answer 1

To prove the given statement, we need to show that the sum of the minimum degree of any vertex in a graph G and the minimum degree of any vertex in its complement graph G' is less than n-1.

Step-by-step explanation:

To prove the given statement, let's start by defining some terms. In graph theory, δ(G) represents the minimum degree of any vertex in graph G, and G' represents the complement of graph G. The complement graph G' has the same vertices as G, but the edges not in G.

Now, let's prove the statement:

1. Since G has n vertices, we can say that each vertex has a maximum degree of n-1, otherwise there would be more than n-1 vertices.
2. Similarly, in the complement graph G', each vertex also has a maximum degree of n-1.
3. Therefore, the minimum degree of any vertex in G is at most n-1, and the minimum degree of any vertex in G' is also at most n-1.
4. Adding the two minimum degrees together, we get δ(G) + δ(G') ≤ 2(n-1).
5. Dividing both sides of the inequality by 2, we have δ(G) + δ(G') ≤ n-1.

Thus, we have proven that δ(G) + δ(G') < n-1 for any graph G with n vertices.