1
$\begingroup$

A planar graph $G$ has no bridges and no two faces have more than one common edge.

Prove that $G$ has two faces that have the same number of edges.

Attempt:

We can use the Euler characteristic formula and properties of graphs.

Understanding the given conditions:

  • The graph is planar.
  • There are no bridges (an edge whose removal increases the number of connected components).
  • No two faces share more than one edge.
  • Applying Euler's formula: For a connected planar graph, Euler's formula states: $V−E+F=2$
  • Let $f_i$ be the number of edges of face $i$. Then $$\sum_{i=1}^F f_i = 2E$$
$\endgroup$
2
  • $\begingroup$ Welcome to Mathematics SE. Take a tour. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. $\endgroup$
    – Another User
    Commented May 24 at 14:30
  • 1
    $\begingroup$ Please edit your question to show your attempt. $\endgroup$
    – Sean Roberson
    Commented May 24 at 14:31

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .