All Questions
Tagged with eulerian-path path-connected
4
questions
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 ...
2
votes
0
answers
24
views
Path / Graph problem with X nodes looking for Y paths with the most similar length.
I have the following graph / path problem:
There is exactly 1 start node and 1 end node.
There are also X (in this case 7) nodes, each connected to all other nodes and the start and end node with ...
1
vote
1
answer
279
views
Need prove a Graphs with n >= 5 with a Euler path and without Hamilton Path and Hamilton Cycle exist.
I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees.
I still have to prove a graph exists that contains ...
2
votes
0
answers
211
views
Show that a graph can be separated in k disjoint trails but with at most one trail of length odd.
Let $G$ be a connected graph containing $2k$ odd vertices, where $k\ge 1$. Prove that $E(G)$ can be partitioned into subsets $E_i$, $1 \le i \le k$, where each subgraph $G[E_i]$ induced by $E_i$ is an ...