Discrete Math: True/False: 1. For any connected graph G, if every vertex of G is

Question

Discrete Math:

True/False:

1. For any connected graph G, if every vertex of G   is of even degree, then Euler circuit exists.

2. There exists a graph with 9 vertices, all of degree 3

3. There is a simple graph with 6 vertices, whose degrees are 2; 2; 2; 3; 4; 4

4. There is no one-to-one correspondence between the set of all positive integers and the set of all odd positive integers because the second set is a proper subset of the first

5. There is a bijective function (i.e., one-to-one and onto function) from the set of integers Z to the set of natural numbers N.

6. The spanning tree for any given graph is always unique

7. A connected graph G with 13 vertices has 12 edges, then G must be a tree

8. simple graph with n vertices and n edges must be a connected graph

Explanation / Answer

1. True.

2. False. The sum of the degrees would be 27, an odd number. For any graph, the sum of the degrees is twice the number of edges, and is thus even.

3. False. Again, the sum of the degrees is odd (17)

4. False. The "proper subset" condition only holds for finite sets. In fact there is a one-to-one correspondence in this case.

5. True.

6. False. Generally, if the graph itself is not a tree, there is no unique spanning tree. For instance, for a cycle, removing any edge gives a distinct spanning tree.

7. True. A connected graph on n vertices with n-1 edges is a tree.

8. False. Consider the case of the graph consisting of two triangles. There are 6 vertices, 6 edges, but the graph is not connected.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.