HOMEWORK 3 .edu
HOMEWORK 3
SOLUTIONS
(1) Show that the graph given below is planar. ?
????????????????*/*/*?/**/?*/*?*/*/?**/*?/*/*?*/*?/**/?*??/*4444444444444444444444?
Solution: To get a plane graph isomorphic to the given graph, we "push" the inner triangle into the lower right corner of the larger triangle and turn it inside out.
???????????????////?////?//?////?//?////?//?////?????//}///////////////////////////?/
2
SOLUTIONS
(2) Let G be a plane graph. If e G, what is the plane dual of the contraction (G ? e) in terms of the plane dual G of G?
Solution: Contracting by an edge e E(G) does not change the faces of G. Hence, (G ? e) has the same vertex set as G. Furthermore, as G ? e has one less edge than G, (G ? e) has one less edge than G. In short,
(G ? e) = G - e.
(3) Let G be a simple connected graph with at least 11 vertices. Prove that either G or its complement G must be nonplanar. Solution: Let G be a graph on n vertices and assume that both G and G are planar. Let m and m be the number of edges in G and G, respectively. The union of the two graphs is the complete graph on n vertices. Thus,
n n(n - 1)
m+m =
=
.
2
2
By Corollary 7.15 in the text, m, m 3n - 6. Therefore,
m + m 6n - 12.
We then have n(n - 1) = m + m 6n - 12 n2 - 13n + 24 0 n < 11. 2
(4) Let G be a simple connected planar graph with less than 12 vertices. Prove that G has a vertex of degree at most 4. Solution: Suppose G has n vertices and m edges and assume that the degree of each vertex is greater than or equal to 5. Again by Corollary 7.15, and the Hand-Shaking Theorem,
5n
dG(u) = 2|E(G)| 6n - 12 n 12.
uV (G)
(5) Let G be a simple connected planar graph with less than 30 edges. Prove that G has a vertex of degree at most 4. Solution: Again assume that the degree of each vertex is greater than or equal to 5. By the Hand-Shaking-Theorem and our assumption on the number of edges
5n
dG(u) = 2|E(G)| < 2 ? 30 = 60 n < 12.
uV (G)
Problem 5 now follows from Problem 4.
HOMEWORK 3
3
(6) Show that K7 is toroidal. Solution: A torus embedding of K7 is given below. By Kuratowski's theorem,
K7 is not planar. Thus, K7 is toroidal.
??tO?otO?otO?otO?ot?O?toO?toO??toOOttotOOtotOOttoOOttoOOttoOOttoOOt?tOOottOOottOOottOOottOOottOOtotOOtot?OOtototOOototOOototOOtootOOtotoOOtotoOOt?toOOttotOOtotOOttoOOttoOOttoOOttOoOt?tOOottOOottOOottOOottOOottOOtotOOtot?O?ot?Oot?Oot?O?to?Oto?Oto?Ot??
(7) Prove that Kn is toroidal if, and only if n {5, 6, 7}. Solution: We have seen in class planar embeddings of K1, K2, K3 and K4.
Therefore, none of these graphs are planar.
We now have toroidal embeddings of K5 and K7. Since, these graphs are not planar, they are toroidal. The graph K6 must also be toroidal, since its genus cannot be less than the genus of K5 or greater than genus of K7.
By Theorem 7.55 from the text,
(n - 3)(n - 4)
(Kn)
. 12
So
when
n
8,
(Kn)
(n-3)(n-4) 12
=
20 12
>
1.
Hence,
Kn
is
not
toroidal
for
those values of n.
(8) What is the maximum number of edges in a graph with n vertices and genus ? Justify, your answer. Solution: The generalization of Euler's Formula gives
n - m + f = 2 - 2.
In class, we saw that
2 f m.
3
4
SOLUTIONS
Therefore we have Hence Thus
2 n - m + m 2 - 2.
3 1 - m 2 - 2 - n. 3 m 3n + 6 - 6.
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- 7th grade math mrs callahan and mr wilson inequalities 1 w
- math 54 selected solutions for week 7 section 5 1 page 241
- igcse mathematics 0580 41 paper 4 extended may jun 2020
- interval notation and linear inequalities section 1 7 math 1300
- go math practice book te g5 geneseo schools
- chapter 2 set theory page 42 university of north georgia
- strategic practice and homework home projects at harvard
- 14 1 lesson big ideas learning
- translating linear inequalities math worksheets 4 kids
- use the number line to write the in inequality use x as the variable
Related searches
- minecraft edu edition
- homework vs no homework facts
- homework vs no homework statistics
- homework vs no homework article
- printable homework for 3 year olds
- free homework online homework assignments
- homework or no homework essay
- grade 3 homework sheets
- connect chapter 3 homework answers
- unit 3 relations and functions homework 4
- unit 3 relations and functions homework 3
- unit 3 relations and functions homework 1