1
$\begingroup$

$G=(V,E). |V| = 25; |E| = 50.$ For every vertex $v \in V$, the degree of that vertex $d(v)=4.$ I am given that the shortest cycles in $G$ are 4-cycles (i.e. with 4 vertices).

For a contradiction I assumed that G is planar. Hence G would have a number of regions/faces $|R|$ with boundary lengths $b(r)$. From this I got:

\begin{equation*} \sum_{r \in R} b(r) = \sum_{v \in V}d(v) = 2|E| = 100, \end{equation*}

and by Euler's theorem: \begin{equation*} |V| - |E| + |R| = |R| - 25 \geq 2 \implies |R| \geq 27. \end{equation*}

So a lower bound on the first summation would be:

\begin{equation*} \sum_{r \in R} b(r) \geq 27 b(r)_{min}. \end{equation*}

where $b(r)_{min}$ is just the length of the smallest boundary for a region. My guess here is to say that $b(r)_{min}$ = 4, given the information I made bold at the start. This would give me the $100 \geq 108$ contradiction I'm after, but this is just a guess and I don't know why/if this is true. I know that the boundaries in a planar drawing are cycles, and maybe these cycles don't change/get shorter when going from planar to non-planar, but again I'm guessing here. Could someone help me finish this proof and tell me if my intuition is right/wrong? Thanks!

$\endgroup$
2
$\begingroup$

Suppose it exist. So each face has at least 4 edges. By double counting between edges and faces we have$$2 |E| \geq 4|F|\implies |E|\geq 2|F|$$ By Euler theorem we have $$|V|-|E|+|F|= 2$$

so $$ |E| \geq 2(2+|E|-|V|)$$

and thus $$2|V|-|E|\geq 4 \implies 50-50\geq 4$$ A contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.