# Tagged Questions

30 views

### Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs?

Why does a 2-colourable simple graph with n nodes have no more than $(n^2/4)$ arcs? I would really appreciate for any kind of explanations.
32 views

### Graph of polytope and hyperplane

Suppose that $P$ is a compact and convex polytope in $R^d$ and let $G$ be the graph of $P$ ($V(G)$ are the vertices of $P$ and $E(G)$ are the $1$-dimensional faces - for example polyedral graphs are ...
105 views

### Flip graph of point set [closed]

Is the ﬂip graph of every point set in $\mathbb R^3$ connected? If not, is there a set with an isolated node? Def: For a point set $S$, the ﬂip graph of $S$ is a graph whose nodes are the set of ...
55 views

### Weighted graphs to minimise the set of distances

$c_{0}$ to $c_{3}$ are given points of the graph and the corresponding weights are $W_{1}$ to $W_{3}$. The objective is to locate $p_{1}$ and $p_{2}$ to minimise the distances $d_{0}+d_{1}$ and ...
137 views

### example that shows that the edge chromatic number may be larger than the maximal degree

What is an example that shows that the edge chromatic number may be larger than the maximal degree ∆ ≤ X’(G)
70 views

### Combinatorial Laplacian Spectrum

The spectrum of the combinatorial laplacian is well understood for a square lattice. What about for other lattices? In particular: let $f: \mathbb{Z}^2 \rightarrow \mathbb{R}$. The usual ...
170 views

### Tilings of the plane

There are many possible tilings (or tesselations) of the plane: periodic ones by a - necessarily - finite number of prototiles (e.g. regular tilings) aperiodic ones by a finite number of prototiles ...
Prove that there exists constant k such that, for all $5v < e$ there is a subgraph of the complete graph of $v$ vertics with crossing number less or equal than $k e^3/v^2$. Any hints for a way to ...