Problem Set 8, 14-16 November

- Let , , be a planar graph
all of whose cycles have length at least four.
(I.e. doesn't contain the triangle as
an induced subgraph, or is
*triangle-free*.) Prove that then the number of edges in is constrained by the inequality . (Note that without the assumption of triangle-freeness one obtains as a corollary to Euler's formula the weaker inequality .) - Show, based on the preceding result, that the graph is not planar, and that the hypercube graphs discussed in Problem Set 7 are planar if and only if .

- Let , , be a planar graph
all of whose cycles have length at least four.
(I.e. doesn't contain the triangle as
an induced subgraph, or is
- Determine the chromatic number of the Petersen graph discussed in Problem Set 6.
- 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.

**[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?- 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 333 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?
- A graph is
*-regular*, if the degree of each of its vertices equals . Prove that every -regular bipartite graph contains a perfect matching. - 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.

- A graph is
- Let
be a family of subsets of some
finite basis set . A
*system of distinct representatives*(also known as a*transversal*) of is any -element set , such that contains exactly one element from each of the sets , . (Note that even though the sets are not in general disjoint, a single element cannot represent more than one set.) Prove that a system of distinct representatives exists for , if and only if for all any union of -sets contains at least elements, i.e.

for all selections of , where for . (*Hint:*Perfect matchings.)