Getting inequality from statement

Question

I have read in book of combinatorics this statement:

any vertex is incidental with at least four edges, and each edge is incidental with two vertices, so $$ 4 |V| \le 2 |E| $$ where V is set of vertices and E set of edges

I suspect that it is easy but... how I can get this inequality from this statement in formal way, not just write and say "it is obvious because it follows from statement".

any vertex is incidental with at least four edges

So $$\forall_v \exists_{e_1, e_2, e_3, e_4, (e_i \neq e_j)} \forall_{k \in \left\{1,2,3,4 \right\}} v \in e_k$$ $$|V| \le 4|E|$$

each edge is incidental with two vertices

$$ |V| = \frac{1}{2}|E| $$ $$ 2|V| = |E| $$

but I don't get result :( Can somebody explain me, how they get this inequality?

Answer 1

Let us count the elements of the set $$X=\{\,(v,e)\mid v\in e\,\}$$ in two different ways.

The canonical projection map $\pi_E\colon X\to E$ is 2-to-1. That means that each element of $E$ has exactly two pre-images, i.e., $|X|=2|E|$. On the other hand, with the canonical projection map $\pi_V\colon X\to V$, each element of $V$ has at least four pre-images. If you don't see immediately that his implies $|X|\ge 4|V|$, pick $4$ pre-images for each $v\in V$ and thereby find a subset $X'\subset X$ such that $\pi_V$ restricted to $X'$ is 4-to-1, hence exactly $|X'|=4|V|$. Putting things together, $$ 4|V|=|X'|\le |X|=2|E|.$$

Answer 2

This is usually called 'double counting' and formally goes like this:

You consider 2 sets of distinct objects, in this case the vertext set $V$ and the edge set $E$ of a graph. You define a relation $R$ between $V$ and $E$ (e.g. $R \subseteq V\times E$) that captures the 'interaction' between those 2 sets that you want to look at. In our case that is the incidence relation, that means for $v\in V$ and $e \in E$ we define

$vRe:\iff \text{$v$ and $e$ are incident in the considered graph}$

Less formally, you can imagine creating a bipartite graph with the vertex set $V \cup E$ and the relation $R$ describes the edges that connect certain vertices of $V$ with certain vertices of $E$.

'Double counting' now means to count the number of elements in the relation $R$ in 2 ways: First, for each element $v \in V$, find statements that describe how many $e \in E$ exists with $vRe$. Then for each element $e \in E$, find statements that describe how many $v \in V$ exists with $vRe$. Since

$$|R|=\sum_{v\in V}|\{e\in E:vRe\}| = \sum_{e\in E}|\{v\in v:vRe\}|$$

you get insights if you have formulas that describe exactly or with an inequality the sets in the above equation.

For this problem, the assumption

any vertex is incidental with at least four edges

translates to

$$\forall v\in V: |\{e\in E:vRe\}| \ge 4$$

and

each edge is incidental with two vertices

translates to

$$\forall e\in E: |\{v\in V:vRe\}| = 2$$

Thus we get

$$|R|=\sum_{v\in V}|\{e\in E:vRe\}| \ge \sum_{v\in V}4 = 4|V|$$

from the first assumption and

$$|R|=\sum_{e\in E}|\{v\in v:vRe\}| = \sum_{e\in E}2 = 2|E|$$

from the second assumption and finally

$$2|E| = |R| \ge 4|V|$$

---

In this problem one can probably easily see the result without the complicated definitons used above, but if the problems get harder, and the relation $R$ to be used trickier, being able to fall back on this formal construct may help to formally write down knowledge gained and see if it helps to prove the final goal.