1

I know that with Contradiction I am suppose to supply a proof that says basically that we keep the first part true but the 2nd part false. For me,

If an un-directed graph has more than 2 vertices of odd degree, it does not have an Euler Path.

I want to prove by contradiction so I am looking at proving that...

If an un-directed graph has more than 2 vertices of an odd degree, it DOES have an Euler path.

I know that each edge can be crossed once onto a vertex and must cross all of them. I am just unsure how I can supply a proof for this. I know this is false by the way as I have tried to prove this right just for fun.

J Crawford
  • 67
  • I want to make sure I understand this, a degree is simply the number of edges connected to it yes? – J Crawford Jun 08 '17 at 00:04
  • 1
    A correction to your understanding of proof by contradiction: You don't want to prove "If an un-directed graph has more than 2 vertices of an odd degree, it DOES have an Euler path." You want to assume you have an undirected graph that has more than two vertices and has an Euler path; then you attempt to derive a false statement which shows that your original assumptions are incompatible. – Christian Sykes Jun 08 '17 at 00:36
  • In fact, if you proved "If an un-directed graph has more than 2 vertices of an odd degree, it DOES have an Euler path", you would not be doing a proof of the desired theorem. You'd be proving a statement that implied that the original theorem is false (and would be much stronger even then that). – Christian Sykes Jun 08 '17 at 00:42
  • You are correct about the definition of degree though. – Christian Sykes Jun 08 '17 at 00:44
  • I guess I literally have no idea what to do here. I hate proofs, god I hope I never have to do this again after this class. Sigh – J Crawford Jun 08 '17 at 00:54
  • The two answers here are two different ways of accomplishing what you asked for. Assume more than two odd degree vertices and and Euler path, and then derive a contradiction. This shows that if you have more than two odd degree vertices, it is not possible that you also have an Euler path. These answers are good, you just have to try to understand them. – Christian Sykes Jun 08 '17 at 00:59
  • A proof is not an arcane or mysterious process. It's simply an argument that a given statement must be true. – Christian Sykes Jun 08 '17 at 01:01
  • Maybe the reason why I am getting to frustrated is because my teacher doesn't let us assume anything and wants every little possible detail, I am just so stressed out I am having a serious mental block and cant picture the two answers in my head. I wont lie I am getting this close to punching a wall..... – J Crawford Jun 08 '17 at 01:03
  • That is indeed what is needed for a proof. If you ignore possible complications, then you may miss a case that completely demolishes the truth of a statement. From a mathematicians standpoint, that isn't good enough. – Christian Sykes Jun 08 '17 at 01:09
  • Thank you everyone for the help, I am going to work on something else before I explode and snap my tablet in half. I will be back in 15 minutes to cool down. – J Crawford Jun 08 '17 at 01:09

2 Answers2

3

Suppose a graph has more than two vertices of odd degree and there is an Euler path starting from vertex A and ending in vertex B. Join A and B by a new edge. Then you have an Euler circuit in this newly formed graph (trace the Euler path from A to B and then join B with A via the new edge). However there is still at least one vertex of odd degree and this contradicts Euler's theorem (a graph has an Euler circuit if and only if every vertex has even degree. )

Prajwal Kansakar
  • 5,391
2

Assume you start the walk at a vertex $w$. Call the $v_1$ and $v_2$ two of the vertices with odd degree that are different from $w$. Now, each time you visit and leave $v_1$ you utilize $2$ of its neighboring edges. Since $v_1$ has odd degree this implies that at some point you need to visit $v_1$, and stay there. The same argument is true for $v_2$, which leads to the desired contradiction.

Christian Sykes
  • 1,027
clark
  • 15,327
  • If I were to walk from w to V1 that means w=1, V1=1, but when I walk to V2 that means w=1, V1=2, V2=1. Still only 2 odd vertices. Right? W-->V1-->V2 – J Crawford Jun 08 '17 at 00:02
  • @JCrawford Yes, but $v_1$ is assumed to have odd degree so we cannot have $v_1=2$ – clark Jun 08 '17 at 00:06
  • oh I see so its W-->V2-->V1 where W=1,V2=2,V1=1. How would this help my proof by contradiction? I cant just say let it be that if we have more than 2 odd vertices then we do have an Euler path because we wont and I wouldn't know even how to start a proof off like that. – J Crawford Jun 08 '17 at 00:11
  • @ChristianSykes I am not assuming that $w$ has even degree. The question assumes we have more than $2$ vertices of odd degree. – clark Jun 08 '17 at 01:17