Search Results

The Held-Karp algorithm for TSP can be modified to count Hamiltonian cycles. The idea is to fix a starting vertex $v \in V$ and inductively count, for every vertex $w \neq v$ and subset $S \subseteq V …

As the graph is self-complementary, by definition there exists some isomorphism $f$ from the graph to its complement. Consider $f$ as a bijection from the vertex-set of the graph to itself (i.e. a per …

There are no such graphs when $n$ is odd, by the handshaking lemma. Conversely, for all even $n \geq 224$, we claim such a graph exists. In particular, given two planar 5-regular graphs $G$, $H$ each …

EDIT: This answer pertains to a misinterpretation of the question before it was later clarified, so does not answer the question as currently stated: Two distinct 4-cycles share a 3-vertex path if …

After further investigation, it appears that disappointingly the answer is 'no', and a proof appears in Lemma 2.4 of Partition Theorems for Subspaces of Vector Spaces (Cates and Hindman, 1975).

Let $\mathbb{F}_q$ be a finite field and $k$ be a positive integer. If we colour each point of the infinite-dimensional projective space $\mathbb{F}_q \mathbb{P}^{\infty}$ with one of $k$ colours, can …

Here's an example (credit: Paul Russell) of the sort of bijection you want to rule out. Question: Find an explicit bijection $f$ between the size-$k$ and size-$(k + 1)$ subsets of $\{1, 2, \dots, 2k+ …

Let $\mathcal{G}$ be the set of isomorphism classes of finite groups. There is an operation $\mathrm{Aut} : \mathcal{G} \rightarrow \mathcal{G}$ which gives the automorphism group of a given group, u …

Yes, your conjecture is true. Suppose otherwise. Then there exists a counterexample $f : \mathcal{P}(8) \rightarrow \{0, 1\}$. For each set $X \in \mathcal{P}(8)$, let the proposition $P_X$ denote $f …

I can prove that all sufficiently large integers are representable. Firstly, observe that there is a unique way, up to isomorphism, to choose three edges $p, q, r$ of the Petersen graph such that the …

Yes, we can. Consider the usual drawing of the Fano plane with 7 vertices, 6 lines, and a circle. Replace the circle with a line through two of the three vertices. Now we have 7 lines with 6 triple i …

I get a total of $62$ by appealling to Burnside's lemma. In particular, note that the objects we are counting are 2-colourings of the vertices of a decagon up to: Rotations; Reflections composed wit …

There is a quadratic-time algorithm for 3-edge-colouring a planar cubic graph, as described in the accepted answer to: https://cstheory.stackexchange.com/questions/2578/complexity-of-edge-coloring-in …

Theorem (difficult): Every planar graph can have its edges directed such that the indegree of each vertex is $\leq 3$. Strengthening (easy): Every plane graph can have its edges directed such that th …

The Leech lattice $\Lambda_{24}$ answers your question with quite a large multiplicity. The unique $24$-dimensional laminated lattice, defined by $\Lambda_0$ being the one-point lattice and $\Lambda …