Looking for polyhedra under two simple but stringent conditionts I noticed usual polyhedra have some vertices joining exactly 3 edges or some triangular faces (or both). Out of curiosity I started wondering if there is a polyhedron with the following constrains: > Each vertex must join at least 4 edges and > > each face must have at least 4 edges I have looked through any number of random examples on the internet and none of them seem to fulfill these conditions, but yet I don't know if such a body is possible at all.

I'll answer the first question. (Asking more than one question per post is discouraged.)

Since each edge is incident at two vertices and adjacent to two faces, your conditions imply

$$e\ge\frac{4v}2=2v\;,$$ $$e\ge\frac{4f}2=2f\;,$$

where $v$, $e$, $f$ are the numbers of vertices, edges and faces, respectively. Adding the two inequalities yields $e\ge v+f$, which contradicts Euler's polyhedron formula, $v-e+f=2$.