3
$\begingroup$

I was studying graph theory when a question came to my mind.

I am referring to a particular way to prove Euler's theorem, viz. the fact that every multigraph (i.e. undirected graph without loops but possibly multiple edges between the same vertices) without isolated vertices, connected and with even degree for every vertex is Eulerian (i.e. admits an Eulerian circuit listing all the edges exactly once).

At a certain point of the proof, it is used the following claim: given a connected multigraph G and a circuit C, the graph G\C obtained removing the edges of C from G is such that every of its connected components contains a vertex of C. I currently can't succeed in proving it, and every source I saw was elusive. How it is provable?

EDIT For those interested, I write here the way I think of it, come up thanks to an answer below. Consider a vertex c of the circuit and an arbitrary vertex v of G\C (i.e. of G). Since G is connected, choose a path P in G from v to c. If P is still a path in G\C, then c proves the claim (since v and c are connected (by P) in G\C). Otherwise, P is not a path in G\C, so it has an arc belonging to C: the ending point (as run by P) of the first of these arcs is both in the G\C-connected component of v (since the previous arcs are not in C and P starts from v) and in C (being an extreme of the arc following the one chosen, which belongs to C).

In addition, the proof does not require C to be a circuit but only a generic path.

$\endgroup$
2
  • 1
    $\begingroup$ Firstly - my sympathies - this is something that I struggled with for ages too. I found it beneficial to visualise what G\C actually looked like compared to G and from there it sort of made sense. Of course, proving it is another matter entirely. Let me check my lecture notes... $\endgroup$
    – Red Five
    Commented May 5 at 9:54
  • $\begingroup$ @RedFive Do you think my proof is correct? $\endgroup$
    – Amanda Wealth
    Commented May 7 at 13:19

1 Answer 1

Reset to default
3
$\begingroup$

Consider two cases

  1. $G \setminus C$ is a single connected component: Then, since $V(C) \subset V(G) = V (G \setminus C)$, all (one) of the connected components of $G \setminus C$ contain a vertex of $C$.

  2. $G \setminus C$ comprises multiple components: Since $G$ was originally a single connected component, each component of $G \setminus C$ was originally connected to at least one other component by some edge that got removed via $C$. Since both vertices of this edge must lie in $C$, and one of them must be in the component, there is a shared vertex between the component and $C$. Hence, the component contains at least one vertex of $C$. Similar logic applies to the other components of $G \setminus C$.

$\endgroup$
1
  • $\begingroup$ Thanks to your answer I succeeded in writing a proof by myself which I added to the question. Do you think it's correct? $\endgroup$
    – Amanda Wealth
    Commented May 5 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .