Next: About this document ...
Up: prob8
Previous: prob8
- 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 .
- 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.
- 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.)
Next: About this document ...
Up: prob8
Previous: prob8
Pekka Orponen
2000-11-09