3
$\begingroup$

Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6?

I know, Theorem: In a connected planar graph where each vertex has the same degree of 6, the number of faces cannot be odd.

Proof: Let G be a connected planar graph with every vertex is degree 6.

By Handshake lemma: $ ∑Deg(Vi) = 2E$

Since $Deg(V) = 6$ for all V,

then $6V = 2E$

$E = 3V$ (Confused here)

Using Euler's for a connected planar:$ V - E + F = 2$

(Confused on this part)

Since V is an integar, 2V is even. Thus F is also even.

Therefore by contradiction a connected planar graph with every vertex of Deg=6 CANNOT have an odd # of faces.

QED.

Is there a better way at proving this? Am I leaving out anything? I feel like i'm over thinking this.

$\endgroup$
5
  • $\begingroup$ Can there even be such a graph ? The only one I can imagine is an infinite triangular grid. $\endgroup$
    – MBobrik
    Apr 22 at 4:09
  • $\begingroup$ @MBobrik I don't think it's possible! I just wanted to make sure my proof was correct or not! :) $\endgroup$
    – Glo
    Apr 22 at 4:12
  • $\begingroup$ @MBobrik if you are asking whether a finite planar graph can be $6$-regular, the answer is "only if you include multigraphs". For example, taking three vertices and three copies of each possible edge works. If you draw it in the plane, it will have $8$ faces. $\endgroup$ Apr 22 at 12:13
  • $\begingroup$ Didn't Kempe prove that every planar graph has a vertex of degree 5 or less? $\endgroup$
    – MJD
    Apr 22 at 14:40
  • $\begingroup$ Note that this is a constructive proof (that if such a graph exists, it has an even number of faces), not a proof by contradiction. $\endgroup$ Apr 22 at 17:40

2 Answers 2

4
$\begingroup$

You are definitely on the right track it seems.

The total degree of $G$ is $2E$ and so we have $6V=2E$ which, when dividing both sides by 2 gives $3V=E$.

Since the graph is planar, we use Euler's formula:

$F+V-E=2$ and replace $E$ with $3V$:

$F+V-3V=2$

$F=2V+2=2(V+1)$

Since $V$ is an integer, this means $F$ must be an even integer.

So the graph described cannot exist.

Statement disproved.

$\endgroup$
1
  • $\begingroup$ Thank you so much! $\endgroup$
    – Glo
    Apr 22 at 4:13
1
$\begingroup$

As noted by MJD, it is well-known that there exists no planar graph that has a minimum vertex degree of 6 or more. Therefore, such a graph cannot exist.

But because of this, both statements

In a connected planar graph where each vertex has the same degree of 6, the number of faces cannot be odd.

and

In a connected planar graph where each vertex has the same degree of 6, the number of faces must be odd.

are true :)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .