1
vote
0answers
42 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
5
votes
1answer
86 views

Which of the players will first draw a triangle?

6 vertices are given. No edges are given at first. Two players play the following game: the first player draws one black edge. Then the second player draws one green edge. Then the first player draws ...
2
votes
0answers
77 views

How many cuts does it take to remove any $n$ vertices from an $m$-dimensional hypercube?

For instance, in $m=3$ dimensions (cube), the following $n=3$ corners (red) can be cut off with a minimum of $C=2$ planes (blue). (Note you are only allowed to cut off the vertices in red.) So what ...
5
votes
1answer
188 views

Characterisation of linearly separable points of a hypercube

Essentially, linearly separable points are just those corners that can be cut off with just one slice as marked out by a hyperplane. E.g. for a cube, the following 4 points (red) are not linearly ...
0
votes
1answer
357 views

Proof of Sperner's Lemma

I am looking for a concise and mathematically robust proof of the Sperner's Lemma. The easiest proof I found so far is Math Pages Blog, but I don't get it without few details. Following is the proof ...
4
votes
2answers
61 views

Planar graph with an exponential amount of matches?

I need a planar graph with an exponential amount of matches. Was wondering is there a good example of this? I'm finding it hard to believe that its possible to have such a graph. I was thinking ...
5
votes
1answer
120 views

Is There a Formalization of Cauchy's $F - E+V = 2$ proof?

Can anyone provide, or direct me to a formalized version of Cauchy's proof that for any convex polyhedron with $F$ faces, $E$ edges and $V$ vertices that $F - E + V = 2$. I am willing to accept the ...
2
votes
1answer
316 views

Minimum number of triangles a polygon of n sides belongs to

Let there be a regular n-sided polygon. A "minimalist" triangle is a triangle which has all vertices on vertices of n. let p be a point on this polygon. What is the minimal number of correct triangles ...
0
votes
2answers
86 views

Permutating dance partners with least distance moved [duplicate]

Possible Duplicate: Gay Speed Dating Problem There are n (even) people at a dance and they dance in pairs. They do not care about gender (it is a very liberal disco). The goal is for each ...
3
votes
0answers
40 views

Internal angle of a vertex of degree $d$ in $\mathbb{E}^2$ and $\mathbb{S}^2$

I am currently working on determining the maximum number of times the minimum spherical distance can occur among $n$ points in $\mathbb{S}^2$, and I have the following question. In $\mathbb{E}^2$, ...
0
votes
0answers
142 views

Generalizing Euler's Polyhedral Formula for Graph Embeddings in Higher Dimensions.

In the plane, Euler's Polyhedral formula tells us that $V - E + F = \chi$, where for graph embeddings we have that $\chi = 1$. Alternatively, we can think of a graph embedding as a simplicial ...