All Questions
Tagged with planar-graphs eulerian-path
12
questions
1
vote
0
answers
37
views
Networks: Covering each edge and starting and ending at the same vertice when repeating edges must be involved.
I'm in year 11 and my question is regarding a certain topic that I've come across in my curriculum. The problem surrounding this question is about creating a path of minimum length that covers each ...
- 11
0
votes
0
answers
92
views
e <= 3v - 6 for planar graph question: why does every face (of a planar graph) have to have at least three sides?
Can't we make a face with just two edges(sides) and two vertices? We just connect those two vertices twice each with different edges and we can make a face between the two edges with only two vertices ...
3
votes
2
answers
182
views
Is this degree sequence planar?
For the degree sequence [6,6,4,4,4,4,2,2,2,2]. Then this graph has $f = 10$ by euler's formula. Let $T$ be the number of triangles. Then the inequalities $2e = 36 \geq 3T + 4(10 - T)$ shows that $T \...
- 651
0
votes
1
answer
774
views
Graph problem about roads built between towns [closed]
There are 10 cities in a country. The Government starts to build direct roads between the cities, but with random access, it can build direct road between two cities even if there is already another ...
- 21
0
votes
1
answer
79
views
Maximal graph not containing a subdivision of $K_5$ is $2$-connected?
I am trying to prove that a graph not containing no subdivisions of $K_5$, such that the addition of any edge would result in the existence of such a subdivision, is $2$-connected.
I already know the ...
- 485
5
votes
2
answers
1k
views
How can one justify if the graph is planar from adjacency matrix?
Given an adjacency matrix of a graph $G$, I was asked to do the following without drawing the graph:
A) Find the vertex of largest degree.
B) Does the graph have an Euler Circuit?
C) Is the graph ...
- 12.7k
2
votes
2
answers
63
views
Graph with conditions
G is a graph whose vertex set is $\{1,2, ... , 82\}$, vertices $i$ and $j$ are adjacent iff $|i-j| \mod 4 = 0 \text{ and } i \neq j$.
(a) Calculate the chromatic number of $G$.
(b) Is $G$ Eulerian?
...
- 824
3
votes
2
answers
1k
views
Is there a simple planar graph with n vertices which has the most possible edges that is also Eulerian
For each $n$, where $n>=3$, are there any graphs in the set of all graphs with $n$ vertices that are simple and planar, and have the most possible number of edges, that also have an Eulerian path ...
- 252
1
vote
2
answers
1k
views
Is there a $6$ vertex planar graph which which has Eulerian path of length $9$?
Let $G$ be a simple graph with Eulerian path of length $9$. There're two non-adjacent vertices $u, v$ in $G$ and if we connect $u$ and $v$ by an edge $G$ is not planar anymore. Does such a graph exist ...
- 2,663
1
vote
1
answer
2k
views
Planar graph has an euler cycle iff its faces can be colored with 2 colors
Planar graph has an euler cycle iff its faces can be properly colored with 2 colors (such way the colors of two faces that has the common edge are different).
I have an idea to consider the dual ...
- 740
5
votes
2
answers
6k
views
Prove that the graph dual to Eulerian planar graph is bipartite.
How would I go about doing this proof I am not very knowledgeable about graph theory I know the definitions of planar and bipartite and dual but how do you make these connection
- 6,708
8
votes
3
answers
22k
views
Prove that Petersen's graph is non-planar using Euler's formula
Prove that Petersen's graph is non-planar using Euler's formula.
I know that $n - m + f = 2$. But should I count $f$ and prove that the summation does not equal to two or solve to get $f =7$ and ...
- 83