retagged by
537 views
0 votes
0 votes

Let $G$ be a simple undirected graph having $n$ vertices with the property that the average of the degrees of the vertices in $G$ is at least $4.$ Consider the following procedure:

$\textsf{Repeatedly delete a vertex from G whose degree is at most 2, until there is no such vertex}.$

Let $H$ be the resulting graph at the end of this procedure. Then,

  1. Show that the graph $H$ is not empty.
  2. Using part $\textsf{(i)}$ above, prove that there exist four distinct vertices $\textsf{a}, \textsf{b}, \textsf{c}$ and $\textsf{d}$ in $H$ such that $\textsf{deg(a)} = \textsf{deg(b)}$ and $\textsf{deg(c)} = \textsf{deg(d)},$ where $\textsf{deg(x)}$ denotes the degree of the vertex $\textsf{x}$.
retagged by

2 Answers

0 votes
0 votes

(i) To show that the graph H is not empty, we can use proof by contradiction. Assume that the resulting graph H is empty after the procedure. This means that every vertex in G had a degree of at least 3, as any vertex with degree 2 or less would have been removed during the procedure. However, this implies that the sum of the degrees in G is at least 3n, since each vertex contributes at least 3 to the sum. But we know that the average degree of the vertices in G is at least 4, so the sum of the degrees is also equal to 4n or greater. This is a contradiction, so the graph H must be non-empty.

(ii) Since the graph H is not empty, it must contain at least one vertex with degree at least 3. Let's call this vertex a. If there is another vertex b in H with the same degree as a, then we are done, as we can choose c and d to be any two distinct neighbors of a and b respectively. So, assume that all other vertices in H have degrees strictly less than deg(a).

Now consider the set of all vertices in G that are adjacent to a. Since a has degree at least 3, this set has at least 3 elements. We know that any vertex in this set with degree 2 or less would have been removed during the procedure to obtain H, so all vertices in this set have degree at least 3. Thus, the sum of the degrees of these vertices is at least 3 times the size of the set, which is at least 9.

Since the average degree in G is at least 4, the sum of the degrees of all vertices in G is at least 4n. We can subtract the degrees of all vertices not adjacent to a to obtain a

 

Aashish Vishwakarma_01_A

 

Let G be a simple undirected graph having n vertices with the property that the average of the degrees of the vertices in G is at least 4. Consider the following procedure: Repeatedly delete a vertex from G whose degree is at most 2, until there is no such vertex. Let H be the resulting graph at the end of this procedure. Then, (i) Show that the graph H is not empty. (ii) Using part (i) above, prove that there exist four distinct vertices a, b, c and d in H such that deg(a) = deg(b) and deg(c) = deg(d), where deg(x) denotes the degree of the vertex x

 

 

(i) To show that the graph H is not empty, we can use proof by contradiction. Assume that the resulting graph H is empty after the procedure. This means that every vertex in G had a degree of at least 3, as any vertex with degree 2 or less would have been removed during the procedure. However, this implies that the sum of the degrees in G is at least 3n, since each vertex contributes at least 3 to the sum. But we know that the average degree of the vertices in G is at least 4, so the sum of the degrees is also equal to 4n or greater. This is a contradiction, so the graph H must be non-empty.

(ii) Since the graph H is not empty, it must contain at least one vertex with degree at least 3. Let's call this vertex a. If there is another vertex b in H with the same degree as a, then we are done, as we can choose c and d to be any two distinct neighbors of a and b respectively. So, assume that all other vertices in H have degrees strictly less than deg(a).

Now consider the set of all vertices in G that are adjacent to a. Since a has degree at least 3, this set has at least 3 elements. We know that any vertex in this set with degree 2 or less would have been removed during the procedure to obtain H, so all vertices in this set have degree at least 3. Thus, the sum of the degrees of these vertices is at least 3 times the size of the set, which is at least 9.

Since the average degree in G is at least 4, the sum of the degrees of all vertices in G is at least 4n. We can subtract the degrees of all vertices not adjacent to a to obtain a lower bound on the sum of the degrees of the vertices adjacent to a. Specifically, this sum is at least 4n - (n - 1 - deg(a)) = 3n + 1 + deg(a). Since this sum is at least 9, we have deg(a) ≥ 4.

Consider the subgraph induced by the vertices adjacent to a. This subgraph has at least 3 vertices and an average degree of at least 4. By the pigeonhole principle, there exist two distinct vertices b and c in this subgraph with the same degree. Let d be any neighbor of b that is not a or c. Then we have deg(b) = deg(c) and deg(a) ≥ 4. Since b and d are distinct, we also have deg(d) ≤ deg(b) - 1. Letting deg(c) = k, we have deg(d) ≤ k - 1 and deg(a) ≥ 4. Since k ≥ 3, we have k - 1 ≥ 2, so there is at least one vertex in the subgraph induced by the neighbors of c that is not b or d. Let e be such a vertex. Then we have deg(e) ≥ k and deg(c) = k, so deg(e) ≥ deg(c). Thus, we have found four distinct vertices a, b, c, and d such that deg(a) ≥ 4, deg(b) = deg(c), and deg(d) ≤ deg(b) - 1.

0 votes
0 votes
I have drawn a Graph with 6 vertices, each with degree 5 so average = (5*6) / 6 = 5 >4

so both of the conditions fullfilled.

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
2 answers
4
admin asked Aug 8, 2022
424 views
Consider the following language $L$ over the alphabet $\Sigma=\{a, b, c\}$. $$ L=\left\{a^{i} b^{j} c^{k} \mid i, j, k \geq 0 \text {, and if } i=1 \text { then } j=k\rig...