Proving "3f ≤ 2e" for Planar Graphs

  • Thread starter kinof
  • Start date
  • Tags
    Graphs
In summary, for a simple, connected, planar graph, the number of faces is less than or equal to two-thirds the number of edges. This can be proven using the concept of double counting, where each edge is counted twice and each face is counted three times. By slicing each edge in two, we can double the number of edges and each edge will still only have one face.
  • #1
kinof
16
0

Homework Statement


Prove that for a simple, connected, planar graph, 3f ≤ 2e where f = faces and e = edges

The Attempt at a Solution


My professor went over this in class, and mentioned something about "double counting," which I do not really understand. I tried saying that it takes 2 counts to define an edge and 3 to define a face, but from here I am not sure what to do as I am unfamiliar with double-counting proofs.

Thanks for the help.
 
Physics news on Phys.org
  • #2
hi kinof! :smile:
kinof said:
My professor went over this in class, and mentioned something about "double counting,"

every edge has exactly two faces, so slice every edge in two, lengthwise …

then you have double the number of edges, and every edge has only one face :wink:
 

FAQ: Proving "3f ≤ 2e" for Planar Graphs

What is a planar graph?

A planar graph is a type of graph in which the edges do not cross each other. This means that the edges can be drawn on a 2-dimensional plane without any intersections.

Why is proving "3f ≤ 2e" important for planar graphs?

Proving "3f ≤ 2e" is important because it is a fundamental property of planar graphs. It helps us understand the structure and complexity of these graphs, and also has important applications in various fields such as network design and circuit theory.

How is "3f ≤ 2e" related to Euler's formula for planar graphs?

Euler's formula states that for a connected planar graph with V vertices, E edges, and F faces, V - E + F = 2. By rearranging this formula, we can get 3f ≤ 2e, which is a stronger inequality that holds for all planar graphs.

What are the common methods for proving "3f ≤ 2e" for planar graphs?

There are a few different methods for proving "3f ≤ 2e" for planar graphs, such as the edge-deletion method, the vertex-deletion method, and the induction method. Each method has its own advantages and is suitable for different types of planar graphs.

Can "3f ≤ 2e" be extended to non-planar graphs?

No, "3f ≤ 2e" only holds for planar graphs. For non-planar graphs, there are other inequalities that can be used to describe their structure and complexity, such as "4f ≤ 2e" for graphs embedded on surfaces with higher genus.

Similar threads

I Finding if a subgraph of a minimal non-planar graph is maximal planar
Replies
1
Views
1K
Prove that there exists a graph with these points such that....
Replies
2
Views
1K
Euler circuit in a directed multigraph
Replies
2
Views
5K
Proving Cut Vertices in Simple Graphs
Replies
2
Views
1K
Strong Induction, Tangled Graph
Replies
3
Views
3K
Proving a (known isomorphic) graph is isomorphic
Replies
6
Views
2K
Prove Graph Theory: All Vertices > 4, At Least 12 Degree 5
Replies
1
Views
1K
Almost All Graphs are Non-Planar
Replies
1
Views
2K
I Euler's Formula for planar graphs - 1 or 2 ?
Replies
2
Views
1K
B 4-colours theorem can be proved visually
Replies
21
Views
1K

Hot Threads

Recent Insights

Back
Top