Introductory Combinatorics
Introductory Combinatorics
5th Edition
ISBN: 9780136020400
Author: Richard A. Brualdi
Publisher: Prentice Hall
bartleby

Concept explainers

bartleby

Videos

Question
Book Icon
Chapter 11, Problem 1E
To determine

The nonisomorphic graphs of order 1, order 2 and order 3, and explain why the answer is for general graphs.

Expert Solution & Answer
Check Mark

Answer to Problem 1E

The number nonisomorphic graphs of order 1 is 1_, of order 2 is 2_ and of order 3 is 4_.

Explanation of Solution

Definition used:

“Two general graphs G=(V,E) and G=(V,E) are called isomorphic, provided that there is a one-to-one correspondence θ:VV between their vertex sets such that, for each pair of vertices x and y of V, there are as many edges of G joining x and y as there are edges of G joining θ(x) and θ(y). The one-to-one correspondence θ is called an isomorphism of G and G.”

Calculation:

By the definition of the isomorphic graphs, it is observed that the two graphs will have same number of vertices and edges having structural similarities.

Consider the case when order of a simple graph is 1. This graph will have exactly 1 vertex.

The only possible simple graph of order 1 is the graph with one vertex having no edge, which is shown below in Figure 1.

Introductory Combinatorics, Chapter 11, Problem 1E , additional homework tip  1

From Figure 1, it is observed that the number of nonisomorphic graphs of order 1 is 1_.

Consider the case when order of a simple graph is 2. This graph will have exactly 2 vertex.

The only possible simple graphs of order 2 is the graph with two vertex having no edge as well as one edge, which is shown below in Figure 2.

Introductory Combinatorics, Chapter 11, Problem 1E , additional homework tip  2

From Figure 2, it is observed that the graphs I and II are nonisomorphic.

Therefore, the number of nonisomorphic graphs of order 2 is 2_.

Consider the case when order of a simple graph is 3. This graph will have exactly 3 vertex.

There are 7 possible simple graphs of order 3, which is shown below in Figure 3.

Introductory Combinatorics, Chapter 11, Problem 1E , additional homework tip  3

From Figure 3, it is observed that the graphs II, III and IV are isomorphic.

Also, the graphs V and VI are isomorphic.

Thus, the nonisomorphic graphs of order 3 are I, II, V and VII which has the number of edges 0, 1, 2 and 3, respectively.

Therefore, the number nonisomorphic graphs of order 3 is 4_.

In the case of general graphs, loops and multi-edges will be present.

That is, for general graphs there is no bound on the number of edges irrespective of the order. Even a single vertex may have many loops.

For example, consider the graph shown below in Figure 4.

Introductory Combinatorics, Chapter 11, Problem 1E , additional homework tip  4

The graph in Figure 4 has multiple edges and loops. There can be many more loops and multiple edges possible in the same graph.

It is known that a graph of order n can have n loops, n(n1) edges and as many multi-edges.

Thus, for general graphs, the number of nonisomorphic graphs of order n will be infinite.

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!
Students have asked these similar questions
(a) Test the hypothesis. Consider the hypothesis test Ho = : against H₁o < 02. Suppose that the sample sizes aren₁ = 7 and n₂ = 13 and that $² = 22.4 and $22 = 28.2. Use α = 0.05. Ho is not ✓ rejected. 9-9 IV (b) Find a 95% confidence interval on of 102. Round your answer to two decimal places (e.g. 98.76).
Let us suppose we have some article reported on a study of potential sources of injury to equine veterinarians conducted at a university veterinary hospital. Forces on the hand were measured for several common activities that veterinarians engage in when examining or treating horses. We will consider the forces on the hands for two tasks, lifting and using ultrasound. Assume that both sample sizes are 6, the sample mean force for lifting was 6.2 pounds with standard deviation 1.5 pounds, and the sample mean force for using ultrasound was 6.4 pounds with standard deviation 0.3 pounds. Assume that the standard deviations are known. Suppose that you wanted to detect a true difference in mean force of 0.25 pounds on the hands for these two activities. Under the null hypothesis, 40 = 0. What level of type II error would you recommend here? Round your answer to four decimal places (e.g. 98.7654). Use a = 0.05. β = i What sample size would be required? Assume the sample sizes are to be equal.…
= Consider the hypothesis test Ho: μ₁ = μ₂ against H₁ μ₁ μ2. Suppose that sample sizes are n₁ = 15 and n₂ = 15, that x1 = 4.7 and X2 = 7.8 and that s² = 4 and s² = 6.26. Assume that o and that the data are drawn from normal distributions. Use απ 0.05. (a) Test the hypothesis and find the P-value. (b) What is the power of the test in part (a) for a true difference in means of 3? (c) Assuming equal sample sizes, what sample size should be used to obtain ẞ = 0.05 if the true difference in means is - 2? Assume that α = 0.05. (a) The null hypothesis is 98.7654). rejected. The P-value is 0.0008 (b) The power is 0.94 . Round your answer to four decimal places (e.g. Round your answer to two decimal places (e.g. 98.76). (c) n₁ = n2 = 1 . Round your answer to the nearest integer.

Chapter 11 Solutions

Introductory Combinatorics

Knowledge Booster
Background pattern image
Math
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Discrete Mathematics and Its Applications ( 8th I...
Math
ISBN:9781259676512
Author:Kenneth H Rosen
Publisher:McGraw-Hill Education
Text book image
Mathematics for Elementary Teachers with Activiti...
Math
ISBN:9780134392790
Author:Beckmann, Sybilla
Publisher:PEARSON
Text book image
Calculus Volume 1
Math
ISBN:9781938168024
Author:Strang, Gilbert
Publisher:OpenStax College
Text book image
Thinking Mathematically (7th Edition)
Math
ISBN:9780134683713
Author:Robert F. Blitzer
Publisher:PEARSON
Text book image
Discrete Mathematics With Applications
Math
ISBN:9781337694193
Author:EPP, Susanna S.
Publisher:Cengage Learning,
Text book image
Pathways To Math Literacy (looseleaf)
Math
ISBN:9781259985607
Author:David Sobecki Professor, Brian A. Mercer
Publisher:McGraw-Hill Education
Finding The Focus and Directrix of a Parabola - Conic Sections; Author: The Organic Chemistry Tutor;https://www.youtube.com/watch?v=KYgmOTLbuqE;License: Standard YouTube License, CC-BY