Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What I'm wanting to prove is what it says in the title of the question.

Or more formally:

$P=(V_p,E_p)$, $Q=(V_q,E_q)$ are two trails of the max length possible / G=(V,E) a connected graph, $(V_p \cup V_q) \subseteq V,(E_p \cup E_q) \subseteq E \Rightarrow$ $\exists v_0 \in V / v_0 \in (V_p \cap V_q)$

My idea was: Suppose you create two trails (P and Q) and they are of the max length possible (they are both on the same connected graph) and they are also disconnected between them. That can't be never true (the fact they are of the max length possible) because if you say it is a connected graph then you can always find a path between any edge of it(that's the definition of connected graph).

And knowing that, you can't never say that you can obtain two trails of it's max length possible and disconnected because you can continue drawing the trail, join them at some edge and doing that you obtain a longer trail.

Sorry if I expressed my idea a bit confusing but I want to let you know that even in Spanish (my native language) is hard for me to write a demonstration right now (I've just started doing these kind of mathematical problems: proving things, this year) so in English is even harder for me.

I would like to know if my reasoning is right or I'm failing at something or maybe if there is a better way to prove this. Or if I should reorder the way I'm proving this...

What I mean by TRAILS is a walk that can repeat vertices but not edges and it's open (in spanish called recorrido), definition taken from the book Ralph Grimaldi - Discrete and Combinatorial Mathematics - 5ed :

enter image description here

share|cite|improve this question
What you write as "trails" is called "paths" in English graph theory jargon. – Henning Makholm Nov 24 '12 at 19:30
up vote 1 down vote accepted

Your idea is right. I would write it down in the following manner:

Suppose $P$ goes from $A$ to $B$ and $Q$ from $C$ to $D$. Since $G$ is connected, there is a trail $R$ from $A$ to $C$. Let $E$ be the first vertex in $R$ (on a journey from $A$ to $C$, following $R$) which is not in $P$ but it starts in some edge $V_p$ of $P$. Note that $E$ does not belong to $Q$ because $V_p \notin Q$. Therefore there is an $F$, which is the first edge in $Q$ on your journey along $R$ after you visited $E$. Now obtain a longer trail by combining the longer one of both the trails from $A$ to $V_p$ or $B$ to $V_p$ along $P$ with the trail from $V_p$ to $F$ with the longer one of the two trails from $F$ to $C$ or $F$ to $C$ along $Q$, achieving the desired contradiction.

share|cite|improve this answer
I think you want $E$ to be an edge, not a vertex. – Marc van Leeuwen Nov 24 '12 at 20:23

You're going in the right direction, I think, but what you have written is not quite convincing. In particular it is not clear how you're proposing to "continue drawing the path" and then "join" them. What if the two given paths both end at vertices of degree 1? Then you cannot just "continue" them.

Hint. You might find this lemma useful:

Suppose $P$ and $Q$ are disjoint paths in a connected graphs. Then there exist a connecting path $R$ with starts at a vertex in $P$, ends at a vertex in $Q$, and is otherwise disjoint from both $P$ and $Q$.

(This is the best you can do in general -- consider for example this graph:



share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.