Chapter 11 Simple Graphs340
the population would change the averages. If he knew graph theory, the researcher
would realize that the nonvirgin male average number of partners will bex.f=m/
times the nonvirgin female average number of partners. What isx?
(d)For purposes of further researach, it would be helpful to pair each female in
the group with a unique male in the group. Explain why this is not possible.
Problems for Section 11.4
Class Problems
Problem 11.3.
For each of the following pairs of graphs, either define an isomorphism between
them, or prove that there is none. (We writeabas shorthand forha—bi.)
(a)G 1 withV 1 Df1;2;3;4;5;6g; E 1 Df12;23;34;14;15;35;45g
G 2 withV 2 Df1;2;3;4;5;6g; E 2 Df12;23;34;45;51;24;25g(b)G 3 withV 3 Df1;2;3;4;5;6g; E 3 Df12;23;34;14;45;56;26g
G 4 withV 4 Dfa;b;c;d;e;fg; E 4 Dfab;bc;cd;de;ae;ef;cfg(c)G 5 withV 5 Dfa;b;c;d;e;f;g;hg; E 5 Dfab;bc;cd;ad;ef;fg;gh;he;dh;bfg
G 6 withV 6 Dfs;t;u;v;w;x;y;zg; E 6 Dfst;tu;uv;sv;wx;xy;yz;wz;sw;vzg
Homework Problems
Problem 11.4.
Determine which among the four graphs pictured in the Figures 11.26 are isomor-
phic. If two of these graphs are isomorphic, describe an isomorphism between
them. If they are not, give a property that is preserved under isomorphism such that
one graph has the property, but the other does not. For at least one of the properties
you choose,provethat it is indeed preserved under isomorphism (you only need
prove one of them).