1. Use Pigeon hole principle to prove that any graph with at least 2 vertices contains two vertices of the same degree. (Hint: Prove by contradiction. (4 points)
2. Given 
(6 Points)
a. Prove the above equation using binomial theorem. (3 Points)
b. Give a combinatorial proof for the given equating. (3 Points)
Homework Answers
1.I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.
Assume that a finite graph G has n vertices. Then each vertex has a degree between n−1 and 0. But if any vertex has degree 0, then no vertex can have degree n−1, so it's not possible for the degrees of the graph's vertices to include both 0 and n−1. Thus, the n vertices of the graph can only have n−1 different degrees,
so by the pigeonhole principle at least two vertices must have the same degree.
2.(a)
By the binomial theorem, we know that we can write
(1+x)n=∑k=0n(nk)xk=(n0)+(n1)x+⋯+(nn)xn
we put x=1
2n=(n0)+(n1)+⋯+(nn)
4n=2n.2n
4n=2n.[(n0)+(n1)+⋯+(nn)]
4n=(n0)2n+(n1)2n+⋯+(nn)2n proved
Add Answer to:
1. Use Pigeon hole principle to prove that any graph with at
least 2 vertices contains...
Question 5. Prove that every graph with at least two vertices contains two vertices with the same...
topic: graph theory
Question 5. Prove that every graph with at least two vertices contains two vertices with the same degree. Then for each n 2 2 give an example of a graph with n vertices which does not have three vertices of the same degree.
Question 5. Prove that every graph with at least two vertices contains two vertices with the same degree. Then for each n 2 2 give an example of a graph with n vertices which...
Use induction on n... 5. Use induction on n to prove that any tree on n2 2 vertices has at least two vertices of degree 1 (a vertex of degree 1 is called a leaf). 5. Use induction on n to prove t...
Use induction on n...
5. Use induction on n to prove that any tree on n2 2 vertices has at least two vertices of degree 1 (a vertex of degree 1 is called a leaf).
5. Use induction on n to prove that any tree on n2 2 vertices has at least two vertices of degree 1 (a vertex of degree 1 is called a leaf).
Q3.a) Show that every planar graph has at least one vertex whose degree is s 5. Use a proof by contradiction b) Using the above fact, give an induction proof that every planar graph can be colored...
Q3.a) Show that every planar graph has at least one vertex whose degree is s 5. Use a proof by contradiction b) Using the above fact, give an induction proof that every planar graph can be colored using at most six colors. c) Explain what a tree is. Assuming that every tree is a planar graph, show that in a tree, e v-1. Hint: Use Euler's formula
Q3.a) Show that every planar graph has at least one vertex whose degree...
49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then...
49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is connected. b. Show that the result in (a) is best possible; that is, for each n 2 2, prove there is a graph with ("2) edges that is not connected.
49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is...
(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use...
(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use this fact to prove the six-color theorem: for any planar graph there exists a coloring with six colors, i.e. an assignment of six given colors (e.g. red, orange, yellow, green, blue, purple) to the vertices such that any two vertices connected by an edge have different colors. (Hint: use induction, and in the inductive step remove some verter and all edges...
Let x and y be vertices of G such that dist(x, y) 2 2. Prove that G contains at least dist(x,y)-1...
Let x and y be vertices of G such that dist(x, y) 2 2. Prove that G contains at least dist(x,y)-1 vertices z other than x and y such that dist(x,y) = dist(x, z) dist(2, y)
Let x and y be vertices of G such that dist(x, y) 2 2. Prove that G contains at least dist(x,y)-1 vertices z other than x and y such that dist(x,y) = dist(x, z) dist(2, y)
using these axioms prove proof number 5 1 - . Axiom 1: There exist at least...
using these axioms prove proof number 5
1 - . Axiom 1: There exist at least one point and at least one line Axiom 2: Given any two distinct points, there is exactly one line incident with both points Axiom 3: Not all points are on the same line. Axiom 4: Given a line and a point not on/ there exists exactly one linem containing Pouch that / is parallel tom Theorem 1: If two distinct lines are not parallet,...
2 (b) Prove that + 3 cos(atx) O has at least two solutions with x €...
2 (b) Prove that + 3 cos(atx) O has at least two solutions with x € (-1,1]. [20 Marks] 1 + x2 (c) State the Rolle's Theorem. [5 Marks] (d) Prove that + 3 cos(1x) = 0 has excalty one solution in [0, 1]. 1 + x2 [20 Marks (Hint:Use proof by contradiction, by supposing more than one root. ]
Question 15: Let n 〉 r 〉 1 . Prove that any n-vertex graph of minimum degree more than n -n/r contains Kr+1 without u...
Question 15: Let n 〉 r 〉 1 . Prove that any n-vertex graph of minimum degree more than n -n/r contains Kr+1 without using Turán's Theorem.
Question 15: Let n 〉 r 〉 1 . Prove that any n-vertex graph of minimum degree more than n -n/r contains Kr+1 without using Turán's Theorem.
Only need 2-5. Need it done ASAP, thank you in advance!! Proofs 1) (1.7.16) Prove that...
Only need 2-5. Need it done ASAP, thank you in advance!!
Proofs 1) (1.7.16) Prove that if m and n are integers and nm is even, then m is even or n is even. * What is the best approach here, direct proof, proof by contraposition, or proof by contradiction why? * Complete the proof. 2) Prove that for any integer n, n is divisible by 3 iff n2 is divisible by 3. Does your proof work for divisibility by...
topic: graph theory
Question 5. Prove that every graph with at least two vertices contains two vertices with the same degree. Then for each n 2 2 give an example of a graph with n vertices which does not have three vertices of the same degree.
Question 5. Prove that every graph with at least two vertices contains two vertices with the same degree. Then for each n 2 2 give an example of a graph with n vertices which...
Use induction on n...
5. Use induction on n to prove that any tree on n2 2 vertices has at least two vertices of degree 1 (a vertex of degree 1 is called a leaf).
5. Use induction on n to prove that any tree on n2 2 vertices has at least two vertices of degree 1 (a vertex of degree 1 is called a leaf).
Q3.a) Show that every planar graph has at least one vertex whose degree is s 5. Use a proof by contradiction b) Using the above fact, give an induction proof that every planar graph can be colored using at most six colors. c) Explain what a tree is. Assuming that every tree is a planar graph, show that in a tree, e v-1. Hint: Use Euler's formula
Q3.a) Show that every planar graph has at least one vertex whose degree...
49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is connected. b. Show that the result in (a) is best possible; that is, for each n 2 2, prove there is a graph with ("2) edges that is not connected.
49.12. Let G be a graph with n 2 2 vertices. a. Prove that if G has at least ("21) +1 edges, then G is...
(2) Recall the following fact: In any planar graph, there exists a vertex whose degree is s 5 Use this fact to prove the six-color theorem: for any planar graph there exists a coloring with six colors, i.e. an assignment of six given colors (e.g. red, orange, yellow, green, blue, purple) to the vertices such that any two vertices connected by an edge have different colors. (Hint: use induction, and in the inductive step remove some verter and all edges...
Let x and y be vertices of G such that dist(x, y) 2 2. Prove that G contains at least dist(x,y)-1 vertices z other than x and y such that dist(x,y) = dist(x, z) dist(2, y)
Let x and y be vertices of G such that dist(x, y) 2 2. Prove that G contains at least dist(x,y)-1 vertices z other than x and y such that dist(x,y) = dist(x, z) dist(2, y)
using these axioms prove proof number 5
1 - . Axiom 1: There exist at least one point and at least one line Axiom 2: Given any two distinct points, there is exactly one line incident with both points Axiom 3: Not all points are on the same line. Axiom 4: Given a line and a point not on/ there exists exactly one linem containing Pouch that / is parallel tom Theorem 1: If two distinct lines are not parallet,...
2 (b) Prove that + 3 cos(atx) O has at least two solutions with x € (-1,1]. [20 Marks] 1 + x2 (c) State the Rolle's Theorem. [5 Marks] (d) Prove that + 3 cos(1x) = 0 has excalty one solution in [0, 1]. 1 + x2 [20 Marks (Hint:Use proof by contradiction, by supposing more than one root. ]
Question 15: Let n 〉 r 〉 1 . Prove that any n-vertex graph of minimum degree more than n -n/r contains Kr+1 without using Turán's Theorem.
Question 15: Let n 〉 r 〉 1 . Prove that any n-vertex graph of minimum degree more than n -n/r contains Kr+1 without using Turán's Theorem.
Only need 2-5. Need it done ASAP, thank you in advance!!
Proofs 1) (1.7.16) Prove that if m and n are integers and nm is even, then m is even or n is even. * What is the best approach here, direct proof, proof by contraposition, or proof by contradiction why? * Complete the proof. 2) Prove that for any integer n, n is divisible by 3 iff n2 is divisible by 3. Does your proof work for divisibility by...
Most questions answered within 3 hours.
-
(63
#14)
which of the following statments best describes how chamging
the concentration of the substances...
asked 1 minute from now -
In the following reaction, which element is undergoing
oxidation: Na2SO3 + N2O --> N2 + Na2SO4...
asked 49 minutes ago -
Which of the following pairs of ions have the same electron
configuration?
I: Br− and Se2−...
asked 3 hours ago -
The Foremost Composite Materials Company is planning a two-day
sales conference for October 19-20. The conference...
asked 3 hours ago -
3) Illustrate the observed pattern of relatedness of organisms
versus adaptations to specific conditions. This means...
asked 4 hours ago -
In winter a lake has a 0.35 m thick ice layer over 1.10 m of
water....
asked 4 hours ago -
Assuming the following has been encrypted with a Vigenere cipher
below, use the method(s) and assumptions...
asked 5 hours ago -
How would I use switch statements to write a program that will
take an input of...
asked 5 hours ago -
Imagine a reaction in which methane gas combusts at a constant
pressure of 1 atm and...
asked 5 hours ago -
Two parallel wires (each 12 m in length) are separated by a
distance of 0.065 m...
asked 5 hours ago -
Suppose there were three masses at the corner of uniform
equilateral triangle. The masses are m1...
asked 5 hours ago -
Situation: A building that is 618 m above the ground floor. How
many times would a...
asked 5 hours ago