next up previous
Next: About this document ... Up: prob8 Previous: prob8

Introduction to Discrete Mathematics, Fall 2000
Problem Set 8, 14-16 November

    1. Let $G = (V,E)$, $\vert V\vert \geq 3$, be a planar graph all of whose cycles have length at least four. (I.e. $G$ doesn't contain the triangle $K_3$ as an induced subgraph, or is triangle-free.) Prove that then the number of edges in $G$ is constrained by the inequality $\vert E\vert \leq 2\vert V\vert-4$. (Note that without the assumption of triangle-freeness one obtains as a corollary to Euler's formula the weaker inequality $\vert E\vert \leq 3\vert V\vert-6$.)
    2. Show, based on the preceding result, that the graph $K_{3,3}$ is not planar, and that the hypercube graphs $H_n$ discussed in Problem Set 7 are planar if and only if $n \leq 3$.

    1. Determine the chromatic number of the Petersen graph discussed in Problem Set 6.
    2. Give an upper bound on the number of colors needed to color the faces of any 3-dimensional convex solid (cube, pyramid, icosahedron etc.) so that no two neighboring faces (i.e. faces separated by a common edge) get the same color.

  1. [Local content.] A university organizes in the same semester courses TTP, JDM, ALTE, APK, DL and MIT. Courses TTP and APK have a number of joint students, as do the courses APK/JDM, JDM/DL, DL/ALTE and ALTE/MIT. How many exam days are needed for the courses' midterm exams, so that no student has two exams on the same day?

  2. A little mouse wants to eat a large cubical piece of cheese. Being a systematic animal, the mouse divides the cheese in its mind into 3$\times$3$\times$3 subcubes, and decides to proceed as follows. It starts eating at one of the corner pieces and eats a whole subcube at a time. After completing one subcube it will move on to one of the neighboring subcubes, finishing up with the subcube at the center of the cheese. Can the mouse succeed in implementing its plan?

    1. A graph $G$ is $d$-regular, if the degree of each of its vertices equals $d$. Prove that every $d$-regular bipartite graph contains a perfect matching.
    2. The prime ministers of all 15 EU countries arrive for a summit meeting in Jyväskylä with 15 municipal dignitaries from the Jyväskylä region. Each prime minister can nominate three people from the Jyväskylä region with whom he/she wants to negotiate. Prove that if no municipal representative gets more than three requests for negotiations (in this case everyone actually gets exactly three requests), then all the requested conferences can be organized in three consecutive sessions, each consisting of 15 parallel bilateral meetings between representatives from the EU and the Jyväskylä region.

  3. Let ${\cal A} = \{A_1,\dots,A_n\}$ be a family of subsets of some finite basis set $U$. A system of distinct representatives (also known as a transversal) of ${\cal A}$ is any $n$-element set $S \subseteq U$, such that $S$ contains exactly one element from each of the sets $A_i$, $i = 1,\dots,n$. (Note that even though the sets $A_i$ are not in general disjoint, a single element cannot represent more than one set.) Prove that a system of distinct representatives exists for ${\cal A}$, if and only if for all $r = 1,\dots,n$ any union of $r$ $A$-sets contains at least $r$ elements, i.e.

    \begin{displaymath}\vert A_{i_1} \cup \dots \cup A_{i_r}\vert \geq r\end{displaymath}

    for all selections of $A_{i_1},\dots,A_{i_r}$, where $i_j \neq i_k$ for $j \neq k$. (Hint: Perfect matchings.)

next up previous
Next: About this document ... Up: prob8 Previous: prob8
Pekka Orponen 2000-11-09