All Questions
Tagged with planar-graphs solution-verification
35
questions
2
votes
1
answer
51
views
Every planar graph with no cycles of length $3,4,5$ is $3$-colorable.
I'm trying to prove that every planar graph with no cycles of length $3,4,5$ is $3$-colorable.
However, I have no opportunity to receive any validation or correction on it, but it would be very ...
- 123
3
votes
2
answers
319
views
Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6?
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 ...
- 69
1
vote
1
answer
69
views
Are all 2-connected graphs planar?
I know that all trees are planar, and so now I'm wondering whether 2-connected graphs are necessarily planar. I would imagine that this is true given that all 2-connected graphs have an ear ...
- 927
0
votes
0
answers
65
views
The final step of proving Kuratowski’s Theorem
Recently when I read the proof of the Kuratowski’s Theorem, I was stuck at the final step where it States 4 cases (Since this proof uses many lemmas, it is difficult to give one context related with ...
- 416
0
votes
2
answers
135
views
Where does my short proof of the 4-colour theorem go amiss?
The proof is essentially a generalisation of the $5$-Colour Theorem:
Proof. Consider the set $S$ of planar graphs which are not $4$-colourable. Choose the graph $G \in S$ that has the least number of ...
- 392
0
votes
1
answer
27
views
Corolary of Euler's identity Theorem in planar graphs
This is a corollary of the book "Graphs and Digraphs" (Chartrand). I just posted for you to evaluate my proof and to let me know what do you think. Thanks!
If $G$ is a plane graph with $n$ ...
- 25
1
vote
0
answers
136
views
If $G$ is a planar graph of girth $g$ that is not a forest, then $e(G)\leq g (v(G) − 2)$
Recall that the girth of a graph is the length of one of its shortest
cycles; if the graph has no cycles, we define its girth as being
infinite. Prove that if $G$ is a planar graph of girth at least $...
- 794
0
votes
0
answers
38
views
Understanding Proof of Graph Theory Problem
I have a question regarding a graph theory problem, and I'm seeking assistance in understanding the provided solution. I comprehend that the solution needs to establish reflexivity, antisymmetry, and ...
- 379
2
votes
0
answers
86
views
Proof of $e\leq3v-6$ for planar graphs without Euler's formula
For a short talk for an audience not familiar with graph theory I want to give an informal proof that $e\leq3v-6$ holds in all planar graphs with $v>2$ and I don't want to use Euler's formula. My ...
- 6,649
3
votes
1
answer
151
views
Prove that regions formed by a planar map vertices even degree can be colored with two colors such that no two neighboring regions have the same color
Prove that regions formed by a planar map all of whose vertices have
even degree can be colored with two colors such that no two
neighboring regions have the same color.
I would like a proof using ...
- 450
0
votes
1
answer
75
views
Prove $\overline{G} $ is not a planar graph
Let $ T = \left(V, E\right) $ be a tree such that $ \left|V\left(T\right)\right| = 8 $. After adding $ 2 $ edges to $ T $, a simple graph $ G = \left(V^{'}, E^{'}\right) $. I need to show that $ \...
- 1,009
2
votes
1
answer
150
views
What way can someone color this image to illustrate the Four Color Theorem?
I've seen similar questions like this and highly doubt this is a disproof or anything, but I still find solutions to these types of problems very satisfying. Here is the map I developed with my ...
12
votes
1
answer
2k
views
Why is this proof for the four color theorem considered wrong?
I'd like to think I found a proof for the four color theorem, but I also know that it took far smarter people than me a computer simulation to prove. Still, I don't see why this logic should be flawed....
- 247
1
vote
1
answer
60
views
How do I prove a graph is non planar?
Using $E\le 3N - 6$
$$13\le 30$$
and using $E \le 2N - 4$
$$13\le 20$$
but I need to show that the graph is non planar
How can I?
Is it a subgraph of $K_{3,3}$?
- 11
0
votes
0
answers
97
views
Proof of Euler's graph theorem: $f=e-v+2$. Is it correct and how can it be improved?
Definitions:
A planar graph is a connected, simple graph.
A face in a planar graph is any $2$D space that is enclosed by edges. The "background" also counts as a face.
$f$ = no. faces
$e$ = ...
- 1,129