Combinatorics, Graph Theory

Graph Theory studies graphs, which are structures made of vertices (nodes) and edges connecting them. It's used to model relationships. Questions cover topics like paths, cycles, connectivity, graph coloring, trees, and analyzing properties of various types of graphs.

• Question

  An `N×N` table is filled with numbers such that all rows are distinct (differing in at least one position). Prove that it is possible to delete a column such that in the remaining table all rows are also distinct.
  (a) Hint

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Proof and Example -> Proof by Contradiction
  Sources:
  • Tournament of Towns, 1979-1980, Main, Spring Question 2

• Question

  In Wonderland, there are `n` cities, and every two of them are connected by a road. The roads meet only in the cities (there are no junctions outside the cities). A wicked magician wants to turn all the roads into one-way streets in such a way that if you leave any city, you can't return to it anymore.

  a. Prove that the wicked magician can do this.

  b. Prove that there exists a city from which one can reach any other city, and that there exists a city from which it is impossible to leave at all.

  c. Prove that there exists a path that passes through all the cities and there is only one such path.

  Topics:

  Combinatorics -> Graph Theory Combinatorics -> Induction (Mathematical Induction) Proof and Example -> Proof by Contradiction

• Question

  In a country there are `100` cities, and from each city `4` roads lead out (a road can only start or end in a city). How many roads are there in this country?

  Topics:

  Combinatorics -> Double Counting Combinatorics -> Graph Theory
  Sources:
  • problems.ru web site

• Question

  A knight moves from square `a1` to square `h8`. Is it possible that along the way it visited every square on the board exactly once?

  Show hint

  Log in here to receive the hint
  Topics:

  Combinatorics -> Double Counting Combinatorics -> Invariants Combinatorics -> Graph Theory Logic -> Reasoning / Logic Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings -> Chessboard Coloring

• Question

  Every person who ever lived on Earth performed a certain number of handshakes (including 0). Prove that the number of people who performed an odd number of handshakes is even.

  Topics:

  Combinatorics -> Double Counting Combinatorics -> Graph Theory Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction

• Question

  The numbers `1`, `2`, `3`, ..., `8` are written on the vertices of a cube. Prove that there exists an edge of the cube such that the difference between the numbers at its endpoints is at least `3`.

  Topics:

  Geometry -> Solid Geometry / Geometry in Space Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Logic -> Reasoning / Logic Proof and Example -> Proof by Contradiction

• Question

  The magical land consists of `25` provinces. Is it possible that each province borders an odd number of other provinces?

  Topics:

  Combinatorics -> Double Counting Combinatorics -> Graph Theory Number Theory -> Division -> Parity (Even/Odd) Proof and Example -> Proof by Contradiction Combinatorics -> Colorings

• Question

  Prove that there is no polyhedron with `7` edges.

  Topics:

  Combinatorics -> Graph Theory Proof and Example -> Proof by Contradiction Geometry -> Solid Geometry / Geometry in Space -> Polyhedra

• Question

  Prove that every polyhedron has at least two faces with the same number of edges.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Graph Theory Geometry -> Solid Geometry / Geometry in Space -> Polyhedra

• Question

  A square is divided into several convex polygons (more than `1`), each of which has a different number of sides. Prove that among these polygons there is a triangle.

  Topics:

  Combinatorics -> Pigeonhole Principle Combinatorics -> Combinatorial Geometry Combinatorics -> Graph Theory Geometry -> Plane Geometry -> Triangles Proof and Example -> Proof by Contradiction Geometry -> Solid Geometry / Geometry in Space -> Polyhedra Minimum and Maximum Problems / Optimization Problems