23

A finite graph has a finite vertex set $V=\{v_1,v_2,\ldots, v_n\}$. Arrange these vertices as points $v_k=(k,0,0)$ $(1\leq k\leq n)$ on the $x$-axis of ${\mathbb R}^3$. Some pairs $v_i$, $v_j$ $(i\ne j)$ are joined by an edge. Assume there are $N\leq{n\choose2}$ edges. Choose $N$ different planes containing the $x$-axis, and draw each occurring edge $\{v_i,...


22

The $4$-vertex digraph a ---> b ---> c d is the smallest example possible. To have the reflexive symmetric transitive closure be different from the symmetric transitive closure, we need an isolated vertex. (If a vertex $v$ has an edge to or from it, then in the symmetric transitive closure, we get the edge $v \to v$.) That isolated vertex will make ...


18

To extend Christian's construction: you can in fact even embed the vertices of your graph in $\mathbb{R}^3$ so that all $N$ edges of the graph are straight lines, and this construction is close to trivial: just make all of the coordinates of the vertices algebraically independent of each other. You can show that this is possible by a dimensionality/counting ...


15

The game is unwinnable iff the largest number is greater than or equal to the sum of all the others, plus 2. If the largest number is this big, then there are too few balls in the other vases to separate all the balls from this vase. If there are fewer balls than this in the largest vase we use induction to prove it is winnable. Firstly if there is only 1 ...


12

We claim the answer is $41$. To see that we can indeed reach $41$ colours, just choose $4$ diagonals and colour each square on those diagonals with a different colour, resulting in $40$ colours, and every other square with the $41$st colour. Suppose there exist two rows that share no colours. That gives at most $10$ different colours, but seeing as each ...


12

As the only thing you're doing when checking commutativity is tracing paths, familiarity with graph theory will not be much use here, unless you just wanted to practise intuiting about tracing paths out. Ultimately, when in doubt, it doesn't hurt to double-check that the pieces you've shown to be commutative do indeed imply commutativity of the entire ...


12

For an $m$ by $n$ array with $mn$ even, consider a lattice on the centres of squares. The path passes through $mn$ lattice points and contains no internal points. So, by Pick's theorem it contains an area of $\frac{mn}{2}-1$. This area consists of unit squares centred on the 'grid points' of the question and so there are $\frac{mn}{2}-1$ enclosed grid points....


11

The main idea here is to create a bijection from the enclosed grid points, to the area of the polygon, to the angle sum on the polygon. We will set this up in reverse. Because the angle sum is a constant, hence the number of enclosed grid points is a constant, which we can then determine. From there, the number of exterior grid points is a constant. Let the ...


9

In graph theory terms, what you are asking for is the longest path formed by an induced subgraph of the $h\times w$ grid graph. This problem (longest induced path) has been well studied for a slightly different case: the $m$-dimensional cube graph. This is the graph formed by taking all subsets of $\{1,\dots,m\}$ as vertices and connect two subsets if they ...


9

It is indeed true that the adjacency matrix of isomorphic graphs will have the same determinant. Indeed, if $A = PBP^T$ for a permutation matrix $P$, then $$ \det(A) = \det(P) \det(B) \det(P^T) = \det(P)^2 \det(B) = \det(B). $$ In fact, we can say more: because $A$ and $B$ are similar matrices, they will have the same eigenvalues. Note that if two matrices ...


8

Pretty sure this is the one you want. https://www.jstor.org/stable/24900867?seq=1#metadata_info_tab_contents


8

This answer isn't fully rigorous but should illustrate the idea. If $n = 1$ or $2$ then the result is trivial to check. So let's consider the case when $n \ge 3$. Suppose by contradiction that there exists a unique path going from one edge to the opposite edge such that both ends of the path are not opposite corners. Let $T$ be the collection of edges that ...


8

The cycle starts and ends in the same vertex, but the path does not.


8

For the "impossible room", recolour the blue squares and yellow goal square black and white in a chessboard pattern, such that the upper-left square is white. Then there is one more white square than black square you start on a white square the goal square is coloured black If it were possible to solve the puzzle without using the Cane of Somaria,...


8

Yes, because a tiebreaker can be modeled as changing the edge weights very slightly to make all edge weights unique. Suppose that edges $e_1, e_2, \dots, e_m$ have weights $w_1, w_2, \dots, w_m \in \mathbb R$. Let $\epsilon$ be the smallest difference between two distinct edge weights. Suppose also that we've written edges $e_1, e_2, \dots, e_m$ in the ...


8

W1hat you are looking for is equivalent to a row-complete Latin square. A Latin square is an $n\times n$ table filled with the numbers $1$ to $n$ so that each row and column has no repeats. A Latin square is further called row-complete if the $n\times (n-1)$ ordered pairs of numbers which occur horizontally adjacently in the square are also all distinct. To ...


8

Consider the graph with 1000 vertices where vertex $i$ is adjacent to $j$ iff $|i-j|$ is neither prime nor square. There are at most $2*(168+31)=398$ vertices which are not adjacent to any point, so each vertex has degree at least $999-398=601>1000/2$. Since each vertex has degree greater than half the size of the graph, it's a well-known theorem that ...


7

You'll have some difficulty, because such a graph does exist. The planar graph below and its complement both have chromatic polynomial $$x^9-18 x^8+141 x^7-627 x^6+1728 x^5-3015 x^4+3242 x^3-1956 x^2+504 x.$$ Found by downloading the $71885$ connected planar graphs from here, and checking the $18$-edge ones for the chromatic polynomial condition using ...


7

A graph with the property that for every pair of nodes, there is a shortest path is sometimes called 'min-unique.' (Usually this concept is used in the directed graph context, where it has complexity theoretic meaning.) I'll discuss below an algorithm to verify min-uniqueness of weighted undirected graphs, with non-negative weights. I suspect that the class ...


7

The graph is bipartite and has $\binom{n+1}{2}+1$ regions, so the problem can only be solvable when $\binom{n+1}{2}+1$ is even: when $n \equiv 1,2 \pmod 4$. This naturally suggests an induction step going from $n$ to $n+4$, adding four lines. Here is our induction hypothesis: an $n$-line configuration where we assume that there is a Hamiltonian cycle. I've ...


7

The rabbit should move up on this first move and then go around the triangle. If the dots were numbered consecutively around the outside of the grid, the starting position has both animals on, say, odd numbered points. As long as they are both on points of the same parity , the rabbit can't catch the turtle. But when he goes around the triangle, he ...


7

The four-colour theorem only stats that if a graph is planar then it can be coloured by at most four colours. It does not state the converse, and indeed $K_{3,3}$ is bipartite – can be coloured with only two colours – but is not planar.


7

Here's a two-step procedure partially borrowed from this question to find a partition. (Actually, maybe it is easier to read the other way around: my explanation here feels better than the one I posted there, so people confused about my answer to that question should read this answer instead.) Number the people around the circle $1, 2, \dots, 100$. Step 1: ...


7

Suppose tree is finite. If no two leafs have common neighbour, then when deleting all leafs we get a graph $H$ with all vertices of degree $2$ or more in $H$. So $H$ has a cycle. But then $T$ has also a cycle. A contradiction.


7

We could use geometry to prove that $K_5$ has no straight-line embedding, for example. To do this, first argue that three of the points $A,B,C$ must form a triangle containing the other two points $D,E$; there's several ways to do this. Then, the line $DE$ can only intersect two sides of $\triangle ABC$ (I mean the line segments); suppose it intersects $AB$ ...


7

You can also have any number of cycles in the graph. If there is a $3$ cycle and a $77$ cycle she can only catch $1$ of the $3$ and $38$ of the $77$ for a total of $39$. If there are $3$ cycles of $3$ and one cycle of $71$, she can catch $38$. Each time a $3$ cycle is removed from an even cycle the count goes down by $1$ until we get to $25\ 3$ cycles and ...


6

Of course, before we find a Hamiltonian cycle or even know if one exists, we cannot say which faces are inside faces or outside faces. However, if there is a Hamiltonian cycle, then there is some, unknown to us, partition for which the sum equals $0$. So the general idea for using the theorem is this: if we prove that no matter how you partition the faces ...


6

I followed the relevant (linked) resources and found the following. Every face has at least three sides $2E \ge 3F$, and at least three faces meet at a vertex $2E \ge 3V$. Combining this with the Euler's formula $V+F=E+2$ for convex polyhedra, one has: $$2F - 4 \ge V \ge F/2 +2$$ And every such pair $(V,F)$ should correspond to at least one convex ...


6

For each number $i$ from $0$ to $9$ let $r_i$ and $c_i$ be the number of rows and columns, respectively, containing the number $i$. Since all ten instances of $i$ are contained in a table with dimensions $r_i$ and $c_i$, we have $r_i\times c_i\ge 10$. It easily follows $r_i+c_i\ge 7$. It follows $\sum_i r_i+c_i\ge 70$. Wthout loss of generality we can ...


6

Here is respectively what $K_{1,3}$, $K_{3,5}$ and $K_{4,8}$ look like. In each graph, the two sets of the bipartition are on the left and on the right respectively. Your $K_{2,3}$ graph is correct but not your $K_{3,3}$ since it misses $3$ edges.


Only top voted, non community-wiki answers of a minimum length are eligible