This is my first question (ever), and I am pretty new to math. So I ask for patience and understanding in advance.

So this is the proof I came up with:

Consider $G = (V,E). $ By definition of Eulerian circuit, $$ \exists\ W: v_0, v_1,\cdots, v_k=v_o $$ And there is no isolated vertex $$ V = \{v_0, v_1,\cdots,v_k \}$$
Take $v_i, v_j \in V $. Consider $ j = i + k $ where $k \in \mathbb{N} $. Then, $ v_j, v_{j+1}, \cdots, v_{j+k} = v_i $ is a walk. Hence, $\exists$ a path between $v_i$ and $v_j$. Hence connected.

  • $\begingroup$ So what is your question? Are you asking whether your proof is correct? $\endgroup$ – Joao Oct 28 '14 at 3:48
  • $\begingroup$ Yes. I feel a little uncomfortable proving graph theorems so I wanted some feed-backs (and perhaps some assurance). $\endgroup$ – Henri L Oct 28 '14 at 4:15

Your proof is generally fine; I can follow your logic. If we really want to be nitpicky:

  • You should probably mention that we are assuming that $G = (V,E)$ has an Eulerian circuit and has no isolated vertices.
  • You should say: "Since $G$ has no isolated vertices, we know that $V = \{v_0, \ldots, v_k\}$."
  • When you take $v_i, v_j \in V$, you should say that they are distinct and that we are assuming, without loss of generality, that $i < j$. This guarantees that $k$ really is a natural number.
  • When you explicitly specify the walk between $v_i$ and $v_j$, you seem to have mixed up $i$ with $j$.
  • It's usually better to use complete English sentences in proofs. Avoid unnecessary logic symbols. Finish your proof with something like: "Hence, there exists a path between $v_i$ and $v_j$ so that $G$ is connected, as desired."
  • 1
    $\begingroup$ Thank you so much! I am beginning to like math (never really liked math back in high school) and this kind of instruction does really help me. Thanks! $\endgroup$ – Henri L Oct 28 '14 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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