All Questions
Tagged with planar-graphs proof-writing
19
questions
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
14
votes
10
answers
3k
views
Can you explain to me why this proof by induction is not flawed? (Domain is graph theory, but that is secondary)
Background
I am following this MIT OCW course on mathematics for computer science.
In one of the recitations they come to the below result:
Official solution
Task:
A planar graph is a graph that can ...
- 294
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
0
votes
1
answer
56
views
Proof of Graph Subdivision
Prove that every simple graph of order $n ≥ 4$ and size at least $2n − 2$ contains a subdivision of $K_4$.
user908851
0
votes
1
answer
1k
views
Show that $K_{r, s}$ is planar if and only if $\min$ {r, s} ≤ 2.
So I've done some draws and this is true, but How can I argument to prove that, by the maximum number of edges in $K$ ?
Or by $d(v)$
Any help?
- 123
3
votes
1
answer
196
views
Show that if $D$ is a planar directed graph without directed edges going in both ways, then $χA (D) ≤ 3$
I have stuck been with this problem.
I know that the chromatic number in a directe graph $χA (D)$ is defined as the smallest integer such that there is a coloration without monochromatic directed ...
- 141
2
votes
1
answer
476
views
How to quickly yet convincingly claim that edge contractions preserve outerplanarity
Let $G$ be a simple outerplanar graph with $n$ vertices. Let the vertex $v \in V(G)$ have degree 2 and be a member of a bounded face formed by a chordless cycle $C$ of more than 3 vertices.
Given the ...
- 79
1
vote
2
answers
202
views
How to show the following for Planar Graphs-Proof Verification
Please tell me where I am wrong:
Consider this graph $G$:
Show that this graph is not planar.
My answer:
Let us consider the vertices $\{0,1,2,3,4\}$.
Then the sub-graph induced by these vertices is ...
- 1,686
0
votes
1
answer
563
views
Finding a maximum connected planar graph to prove the four colour theorem
Like many, I have been done a lot of reading of the Four Colour Theorem and there is one question that is vexing me to the point where I am sure I am misunderstanding. I hope that someone could help ...
3
votes
2
answers
838
views
Proof that a Octahedron graph is 3-colorable?
I worked on a problem that gives an adjacency matrix and lets you draw a graph from that. After some time I found that the graph is a) planar and b) not any planar graph, but a Octahedron.
The next ...
- 2,493
1
vote
1
answer
4k
views
Prove that no connected planar graph with $\lt 12$ faces and $\gt 3$ degree each vertex has a face with %\le 4$ bounding edges
I've spent the last 7 hours trying to solve this one problem, no kidding. The textbook is absolutely useless and there's nothing helpful on the internet.
Let $G$ be a simple plane graph with fewer ...
- 13
3
votes
1
answer
646
views
Prove that $G$ or $\bar G$ must be nonplanar if G has 11 vertices.
The exact problem is the following: "Let G be a graph with 11 vertices. Prove that $G$ or $\bar G$ must be nonplanar.
I went to my professor to discuss the proof, but she said it didn't quite work, ...
- 143
2
votes
1
answer
547
views
Bipartite Planar Graph [closed]
Prove that a bipartite (ie, two-colorable) planar graph with $E$ edges and $V$ vertices satisfies: $E\leq 2V-4$, for $V\geq 3$.
user387795
3
votes
1
answer
1k
views
Questions of the form "let $G$ be a planar graph such that every face is a...$" Prove that...
Let $G$ be a planar graph with degrees all at least three. Suppose we can draw $G$ in a plane such that every face is a square. Prove the number of vertices of degree three is greater than the number ...
0
votes
2
answers
4k
views
Each regional of a maximal planar graph is a triangle
Show that every region of a maximal planar graph is a triangle.
A planar graph G is called maximal planar if the addition of any edge to G creates a nonplanar graph.
Will this proof use the ...
- 1,245