This is a homework problem and my solution. I think I get the main ideas and understand what is going on, but I need to work on my proof writing. I don't get full credit when I think I should get a little better than what I have been getting.
Theorem: For $n \geq 2$, planar graphs with $n$ ve...
@TheGreatDuck Might I suggest you just do this, or this. Hope it helps.
The latter finds questions wich have an answer, but with none upvoted (so the system considers them unanswered). Perhaps you might enjoy reading through some of those answers and, if deserved, give them an upvote or add a better answer.
Let $G = (V, E)$ be a directed acyclic graph. For each vertex $v \in V$, define the ancestors of $v$ to be the set of vertices $u \in V$ such that there exists a directed path from $u$ to $v$. Similarly, define the descendants of $v$ to be the set of vertices $w \in V$ such that there exists a di...
What is the largest possible number of edges in a planar graph without $3$- or $4$-cycles?
I've been unsuccessfully trying to solve this problem from my book. I know that every planar graph without $3$-cycles has at most $2n - 4$ edges, though I'm not sure about graphs without $4$-cycles.
Here's what I've got so far. I'm stuck on how to proceed. I believe I need to plug back into Euler's formula, but I'm not getting what I'm looking for by doing that. Where is the denominator of $3$ coming from in the result? Can you please check over my proof for any incorrect statements, and hel...
What is the largest possible number of edges in a planar graph without $3$- or $4$-cycles?
I've been unsuccessfully trying to solve this problem from my book. I know that every planar graph without $3$-cycles has at most $2n - 4$ edges, though I'm not sure about graphs without $4$-cycles.
