1. Prove that it is impossible to have a group of nine people at a party...

1. Prove that it is impossible to have a group of nine people at a party such that each one knows exactly five others in the group.
2. Let G be a graph with n vertices, t of which have degree k and the others have degree k+1. Prove that t = (k+1)n - 2e, where e is the number of edges in G.
3. Let G be a k-regular graph, where k is an odd number. Prove that the number of edges in G is a multiple of k.
4. Let G be a graph with n vertices and exactly n-1 edges. Prove that G has either a vertex of degree 1 or an isolated vertex.
5. Show that the k-cube has 2^k vertices and k2^(k-1) edges and is bipartite.
6. Prove that if G is a simple graph with at least two vertices, then G has two or more vertices of the same degree.

Solutions

Expert Solution

The solution of the above question is given below

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

A group of college students want to have a party. They need to decide if they...

A group of college students want to have a party. They need to decide if they want to have it at the Beach (B) or at the Park (P) or in a Warehouse (W). They were ask to list in order their 1st, 2nd, and 3rd choice of where they want to have the party. Use the following table and answer the following questions. SHOW YOUR WORK to receive full credit. 10 students 8 students 13 students 1 st choice...

The nine entries of a 3×3 grid are filled with −1, 0, or 1. Prove that...

The nine entries of a 3×3 grid are filled with −1, 0, or 1. Prove that among the eight resulting sums (three columns, three rows, or two diagonals) there will always be two that add to the same number.

ERDQuestion A group of students attend an end of semester party. The party was described by...

ERDQuestion A group of students attend an end of semester party. The party was described by one attendee as‘very exciting’. Students played computer gamestill almost midnight! Each of the students has a name and a Player Name e.g. Fred Smith "The Slayer". Each of the games played has a name and a description. Each console has a unique serial no, name and the year of manufacture. The games can all be played on any ofthe various consolesthat have been broughtto...

In a group of 40 people, how many cases that two or more people have the...

In a group of 40 people, how many cases that two or more people have the same birthday? NOT probability, cases please.

BACKGROUND: Given a group of 'n' people, the odds that at least two people have the...

BACKGROUND: Given a group of 'n' people, the odds that at least two people have the same birthday are much higher than you would think. PLEASE WRITE CODE IN C++ The program takes no input. Assumptions: 1. There is an equal chance of birthday landing on any day of the year. 2. We are not considering a leap year (only 365 days) The simulation will be run in the following manner: 1. For a group size 2, assign a random...

1. Please list and discuss nine services and products that are provided to all people in...

1. Please list and discuss nine services and products that are provided to all people in our country "free" at the point of sale, (with the costs paid for by taxation). 2. Which one service or product on your list is the most important, in your opinion? Why? 3. Which one service or product on your list is the least important, in your opinion? Why? 4. If you had to add one more service or product on to the list,...

What is the probability that in a group of three people at least two will have...

What is the probability that in a group of three people at least two will have the same birth month? (Assume that all sequences of three birth months are equally likely.) (b) What is the probability that in a group of n people, n ≤ 12 , at least two will have the same birth month? (c) What is the probability that in a group of n people, n > 12 , at least two will have the same birth...

Question