Found problems: 11
In a graph with $8$ vertices that contains no cycle of length $4$, at most how many edges can there be?
Given a positive integer number $n$, determine the maximum number of edges a triangle-free Hamiltonian simple graph on $n$ vertices may have.
Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face $F$ of the polyhedron are written the number of edges of $F$ belonging to the route of the first ant and the number of edges of $F$ belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers?
[i]Proposed by Nikolai Beluhov[/i]
Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face $F$ of the polyhedron are written the number of edges of $F$ belonging to the route of the first ant and the number of edges of $F$ belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers?
[i]Proposed by Nikolai Beluhov[/i]
Prove that in each polyhedron there exist two faces with the same number of edges.
A graph has $17$ points and each point has $4$ edges. Show that there are two points which are not joined and which are not both joined to the same point.
A graph has $30$ points and each point has $6$ edges. Find the total number of triples such that each pair of points is joined or each pair of points is not joined.
In a country every two towns are connected by exactly one one-way road. Each road is intended either for cars or for cyclists. The roads cross only in towns, otherwise interchanges are used as road junctions. Show that there is a town from which you can go to any other town without changing the means of transport.
Initially $A$ selects a graph with \( 2221 \) vertices such that each vertex is incident to at least one edge. Then $B$ deletes some of the edges (possibly none) from the chosen graph. Finally, $A$ pays $B$ one lev for each vertex that is incident to an odd number of edges. What is the maximum amount that $B$ can guarantee to earn?
Prove that in each polyhedron there exist two faces with the same number of edges.
Two ants are moving along the edges of a convex polyhedron. The route of every ant ends in its starting point, so that one ant does not pass through the same point twice along its way. On every face $F$ of the polyhedron are written the number of edges of $F$ belonging to the route of the first ant and the number of edges of $F$ belonging to the route of the second ant. Is there a polyhedron and a pair of routes described as above, such that only one face contains a pair of distinct numbers?
[i]Proposed by Nikolai Beluhov[/i]