Let G be cubic plane graph such that every face boundary of G is of length divisible by four. By an indirect proof, it follows that the number of vertices in G must be divisible by eight.
Can you prove this by an elementary method? (which should be possible I think, though I don't have such a proof).
Disclaimer: Cross-posted in stackexchange (https://cstheory.stackexchange.com/q/50959/47855).
This is NOT an answer to the question; rather a comment on the answer by Peter Breuer .
Yes, a cubic graph is graph such that every vertex has degree three. And, by "face boundary" I mean the edges that form the boundary of a face, and "length" means the number of edges in that boundary.
Thank you for your effort. But, the argument "the number of edges must be some multiple of 4 times the number of faces" seems wrong to me. For instance, a graph can have exactly 3 faces with boundary lengths 4,8 and 8 respectively, yet 4+8+8 is not a multiple of F=3.
Remark: The above one is not an actual example though; a graph with 10 faces and face boundaries 8,8,4,4,...,4 is a proper counterexample to the argument. One such graph is the circular ladder graph CL_8 (i.e. there are two 8-vertex cycles, one inner cycle and one outer cycle, and there is a perfect matching between vertices of these cycles in a one-to-one fashion).
Peter, the answer to your last question: the graph is planar, hence connected.
Unfortunately, your claim leading to E=2NF looks credible but is wrong. If all the faces are 4m-gones (with the same m), the claim holds, but not in general. The counterexample given by Cyriac shows it.
EDIT: In fact, the only convenient graph with identical faces is the cube CL4.
@Peter Breuer
Your idea of splitting large faces is nice.
An indirect proof is a proof that proves a result indirectly in terms of some other notion. E.g.: the indirect proof to this I know uses variants of graph coloring and graph homomorphisms.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs