6. Consider the complete graph Kn for n ≥ 3. Color r of the vertices in K, red and the remaining n − r(= g) vertices green. For any two vertices v, w in Kn, color the edge {v, w} (1) red if v, w are both red, (2) green if v, w are both green, or (3) blue if v, w have different colors. Assume that r≥ g. 1 a) Show that for r = 6 and g = 3 (and n = 9) the total number of red and green edges in K9 equals the number of blue edges in K9. b) Show that the total number of red and green edges in K, equals the number of blue edges in K, if and only if n = r+g, where 9, r are consecutive triangular numbers. [The triangular numbers are defined recursively by t₁ = 1,tn+1 tn = n(n+1)/2. Hence t₁ = 1, t2 = 3, t3 = 6,...] = = t + (n+1), n > 1; so
6. Consider the complete graph Kn for n ≥ 3. Color r of the vertices in K, red and the remaining n − r(= g) vertices green. For any two vertices v, w in Kn, color the edge {v, w} (1) red if v, w are both red, (2) green if v, w are both green, or (3) blue if v, w have different colors. Assume that r≥ g. 1 a) Show that for r = 6 and g = 3 (and n = 9) the total number of red and green edges in K9 equals the number of blue edges in K9. b) Show that the total number of red and green edges in K, equals the number of blue edges in K, if and only if n = r+g, where 9, r are consecutive triangular numbers. [The triangular numbers are defined recursively by t₁ = 1,tn+1 tn = n(n+1)/2. Hence t₁ = 1, t2 = 3, t3 = 6,...] = = t + (n+1), n > 1; so
Fundamentals of Information Systems
8th Edition
ISBN:9781305082168
Author:Ralph Stair, George Reynolds
Publisher:Ralph Stair, George Reynolds
Chapter3: Database Systems And Applications
Section: Chapter Questions
Problem 2.1DQ
Related questions
Question
6. Consider the complete graph Kn for n ≥ 3. Color r of the vertices in Kn red and the
remaining n − r(= g) vertices green. For any two vertices v, w in Kn, color the edge {v, w} (1)
red if v, w are both red, (2) green if v, w are both green, or (3) blue if v, w have different colors.
Assume that r ≥ g.
a) Show that for r = 6 and g = 3 (and n = 9) the total number of red and green edges in K9
equals the number of blue edges in K9.
b) Show that the total number of red and green edges in Kn equals the number of blue edges
in Kn if and only if n = r + g, where g, r are consecutive triangular numbers.
[The triangular numbers are defined recursively by t1 = 1, tn+1 = tn + (n + 1), n ≥ 1; so
tn = n(n + 1)/2. Hence t1 = 1, t2 = 3, t3 = 6, . . . ]
PS: Please type with the correct one and do not use ChatGPT to give me the answer.
![6. Consider the complete graph Kn for n ≥ 3. Color r of the vertices in K, red and the
remaining n − r(= g) vertices green. For any two vertices v, w in Kn, color the edge {v, w} (1)
red if v, w are both red, (2) green if v, w are both green, or (3) blue if v, w have different colors.
Assume that r≥ g.
1
a) Show that for r = 6 and g = 3 (and n = 9) the total number of red and green edges in K9
equals the number of blue edges in K9.
b) Show that the total number of red and green edges in K, equals the number of blue edges
in K, if and only if n = r+g, where 9, r are consecutive triangular numbers.
[The triangular numbers are defined recursively by t₁ = 1,tn+1
tn = n(n+1)/2. Hence t₁ = 1, t2 = 3, t3 = 6,...]
=
= t + (n+1), n > 1; so](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F6517b75e-c73d-4d99-82de-f9576206bce1%2Ff193478d-9d6f-4e7d-8130-d6fcf6357be1%2Fv0uur3j_processed.png&w=3840&q=75)
Transcribed Image Text:6. Consider the complete graph Kn for n ≥ 3. Color r of the vertices in K, red and the
remaining n − r(= g) vertices green. For any two vertices v, w in Kn, color the edge {v, w} (1)
red if v, w are both red, (2) green if v, w are both green, or (3) blue if v, w have different colors.
Assume that r≥ g.
1
a) Show that for r = 6 and g = 3 (and n = 9) the total number of red and green edges in K9
equals the number of blue edges in K9.
b) Show that the total number of red and green edges in K, equals the number of blue edges
in K, if and only if n = r+g, where 9, r are consecutive triangular numbers.
[The triangular numbers are defined recursively by t₁ = 1,tn+1
tn = n(n+1)/2. Hence t₁ = 1, t2 = 3, t3 = 6,...]
=
= t + (n+1), n > 1; so
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 6 images
Recommended textbooks for you
Fundamentals of Information Systems
Computer Science
ISBN:
9781305082168
Author:
Ralph Stair, George Reynolds
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
Fundamentals of Information Systems
Computer Science
ISBN:
9781305082168
Author:
Ralph Stair, George Reynolds
Publisher:
Cengage Learning
Operations Research : Applications and Algorithms
Computer Science
ISBN:
9780534380588
Author:
Wayne L. Winston
Publisher:
Brooks Cole
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr
Principles of Information Systems (MindTap Course…
Computer Science
ISBN:
9781285867168
Author:
Ralph Stair, George Reynolds
Publisher:
Cengage Learning