2
$\begingroup$

All graphs considered here are finite, simple and undirected.

Let $\mathscr{G}$ denote the class of cubic plane graphs for which all face boundaries are of length divisible by four. The 3-cube $Q_3$ is a member of $\mathscr{G}$ (perhaps, the smallest member of $\mathscr{G}$). By an indirect proof, one can prove the following by combining some existing results:

  • For every graph $G\in\mathscr{G}$, the number of vertices in $G$ is divisible by 8.

Can you prove this by an elementary method?
I would like to get a feel of the class $\mathscr{G}$; so, indirect proofs are also welcome (as they may show some properties of the class I am not aware of).

$\endgroup$
1
$\begingroup$

By the Euler characteristic and double counting edges with the cubic assumption, we get $v=2f-4$. So v is even, and it suffices to prove that f is even too. By the defining property of $\mathcal{G}$ and double counting edges, $\sum_{k \equiv 0 mod 4} k f_k=2e$, where $f_k$ is the number of faces of degree $k$. Reducing mod 4, we get that $2e \equiv 0 mod 4$, and thus that $e$ is even. By the Euler characteristic we deduce that $f$ is even which concludes the proof.

$\endgroup$
2
  • $\begingroup$ Oops, sorry. I gave the wrong number in the question. It should be "the number of vertices in $G$ is divisible by 8". I have updated the question now (the constant was 4 in the earlier version of the question). $\endgroup$ Jan 11 at 13:25
  • 2
    $\begingroup$ That $v$ is divisible by 4 can be shown much more easily by double counting: the number of incident vertex-face pairs is, on the one hand, $3v$, on the other hand, the sum of the number of sides of all faces, which is a multiple of 4. (In your notation: $\sum_kkf_k=3v$.) $\endgroup$ Jan 13 at 14:25

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.