Question 1

Given the degree sequence $$\{1, 2, 3, 4, 4\}$$, does a simple graph with this degree sequence exist? If not, why?

Accepted Answer

No, because the sum of the degrees is odd, which is impossible for a simple graph.

Question 2

Consider the degree sequence $$\{2, 2, 2, 2, 2, 2\}. $$Which of the following statements is true?

Accepted Answer

A simple graph exists and it must be a cycle with 6 vertices.

Question 3

Given the degree sequence $$\{1, 1, 2, 3, 4, 5, 5\}$$, does a simple graph exist? Why or why not?

Accepted Answer

No, because the sum of the degrees is odd.

Question 4

Which of the following degree sequences cannot correspond to a simple graph?

Accepted Answer

$$\{3, 3, 3, 3, 3\}$$

Question 5

A degree sequence $$\{0, 1, 3, 4, 4, 5, 7\} is $$proposed for a simple graph. What is the main reason this sequence is not possible?

Accepted Answer

The sum of the degrees is odd.

Question 6

Which of the following is a necessary condition for a degree sequence to correspond to a simple graph?

Accepted Answer

The sum of the degrees must be even.

Question 7

Given the degree sequence $$\{2, 2, 2, 4, 4, 6\}$$, which of the following is true?

Accepted Answer

No simple graph exists because the highest degree (6) is greater than or equal to the number of vertices (6).

Question 8

Suppose you are designing a network where each computer must be connected to exactly three others. If there are five computers, is this possible?

Accepted Answer

No, because the sum of the degrees is odd.

Question 9

Given the degree sequence $$\{1, 1, 2, 2, 5, 5\}$$, what is the first step to determine if a simple graph exists?

Accepted Answer

Check if the sum of the degrees is even.

Question 10

A social network has 7 people. Is it possible for their degrees to be $$\{2, 3, 3, 4, 5, 5, 6\} in a $$simple graph? Why or why not?

Accepted Answer

No, because the sum of the degrees is odd.

Question 11

Which of the following degree sequences could represent a simple graph?

Accepted Answer

$$\{2, 2, 2, 2, 2, 2\}$$

Question 12

If a degree sequence contains a vertex of degree 0 and another of degree $$n-1 ($$where $$n is $$the number of vertices), what can you conclude?

Accepted Answer

No simple graph exists because the vertex of degree $$n-1$$ must be connected to all others, including the isolated vertex.

Question 13

Given the degree sequence $$\{1, 1, 2, 2, 2, 2, 3, 3\}$$, what is the sum of the degrees, and what does this tell you?

Accepted Answer

The sum is 16, which is even, so a simple graph may exist.

Question 14

A degree sequence $$\{1, 2, 2, 3, 3\} is $$proposed for a simple graph. Which of the following is true?

Accepted Answer

A simple graph exists because the sum of the degrees is even and all degrees are less than the number of vertices.

Question 15

Which of the following degree sequences is not possible for a simple graph with 5 vertices?

Accepted Answer

$$\{1, 1, 1, 1, 2\}$$

Question 16

Suppose you have a degree sequence $$\{2, 2, 3, 3, 4, 6\}. $$What is the main reason this sequence cannot correspond to a simple graph?

Accepted Answer

The highest degree (6) is equal to the number of vertices, which is not allowed in a simple graph.

Question 17

A group of 7 friends wants to form a network where their degrees are $$\{2, 2, 3, 4, 4, 5, 5\}. Is $$this possible?

Accepted Answer

Yes, because the sum of the degrees is even and all degrees are less than the number of vertices.

Question 18

Which of the following is a necessary step in determining if a degree sequence can be realized as a simple graph?

Accepted Answer

Check if the sum of the degrees is even.

Guided Practice: Determining the Existence of Simple Graphs for Given Degree Sets

스터디 가이드 - 연습 문제