Proving a formula for # of edges

[Mr Davis 97]

Homework Statement

If $v$ is an integer greater than or equal to $2$, then $P_v$ is the graph having vertex set $\{1,2,3, \dots, v \}$ and edge set $\{\{1,2 \}, \{2,3 \}, \{3,4 \}, \dots, \{v-1,v \} \}$. Prove that this graph has $v-1$ edges.

Homework Equations

The Attempt at a Solution

Induction:
With $P_2$, we have $\{1,2\}$ and $\{ \{1,2\} \}$, so there is $2-1 = 1$ edge.
Suppose that $P_k$ has $k-1$ edges. Then $P_{k+1}$ has $k$ edges because its edge set is $\{\{1,2 \}, \{2,3 \}, \{3,4 \}, \dots, \{k-1,k \}, \{k,k+1\} \}$.I feel like I'm doing something wrong, but I'm not sure. Is this induction right? Is there a way to do it without induction?

 

[member 587159]

Homework Statement

If $v$ is an integer greater than or equal to $2$, then $P_v$ is the graph having vertex set $\{1,2,3, \dots, v \}$ and edge set $\{\{1,2 \}, \{2,3 \}, \{3,4 \}, \dots, \{v-1,v \} \}$. Prove that this graph has $v-1$ edges.

Homework Equations

The Attempt at a Solution

Induction:
With $P_2$, we have $\{1,2\}$ and $\{ \{1,2\} \}$, so there is $2-1 = 1$ edge.
Suppose that $P_k$ has $k-1$ edges. Then $P_{k+1}$ has $k$ edges because its edge set is $\{\{1,2 \}, \{2,3 \}, \{3,4 \}, \dots, \{k-1,k \}, \{k,k+1\} \}$.I feel like I'm doing something wrong, but I'm not sure. Is this induction right? Is there a way to do it without induction?

It's fairly straightforward to see that the edge sets contains v-1 elements no? Doesn't this solve the question? I haven't done graph theory lately so I might be missing something.

 

[Mr Davis 97]

It's fairly straightforward to see that the edge sets contains v-1 elements no? Doesn't this solve the question? I haven't done graph theory lately so I might be missing something.

It's straightforward to see, but don't I still need to prove it? I guess my main question then is since it is so self-evident, what would constitute a proof? Could I say, the cardinality of the edge set is clearly v-1?

 

[member 587159]

It's straightforward to see, but don't I still need to prove it? I guess my main question then is since it is so self-evident, what would constitute a proof?

If you really want to, you can set up a natural bijection between the edge set $\{\{i,i+1\}\mid i \in \{1, \dots, v-1\}\}$ and $\{1, \dots v-1\}$. But this seems overkill.

The statement is so obvious to me that I wouldn't even bother to give a proof.

 

[fresh_42]

I don't get it. Haven't you already numbered all edges by the notation of the set? All edges are of the form $\{\,i,i+1\,\}$. So if you formally define the numbering $n : \{\,\{\,i,i+1\,\}\, : \,1\le i \le v-1\,\} \longrightarrow \{\,1,\ldots,v-1\,\}$ by $n(i) =min\{\,i,i+1\,\}$ which is a bijection and $\operatorname{im}n = \{\,1,\ldots,v-1\,\}$ you have the result. But as @Math_QED already said: a bit of an overkill.

 

[Mr Davis 97]

What about this: If $v$ is an integer greater than or equal to $4$, $W_v$ is the graph having vertex set $\{1,2,3, \dots, v \}$ and edge set $\{ \{1,2\}, \{1,3\}, \dots, \{1,v\}, \{2,3\}, \{3,4\}, \dots, \{v-1,v\}, \{v,2\} \}$. Prove this graph has $2(v-1)$ edges. How would I go about proving this? It seems a little less obvious...

 

[fresh_42]

What about this: If $v$ is an integer greater than or equal to $4$, $W_v$ is the graph having vertex set $\{1,2,3, \dots, v \}$ and edge set $\{ \{1,2\}, \{1,3\}, \dots, \{1,v\}, \{2,3\}, \{3,4\}, \dots, \{v-1,v\}, \{v,2\} \}$. Prove this graph has $2(v-1)$ edges. How would I go about proving this? It seems a little less obvious...

Formally also with a numbering. In this example it's only more work to do it, such that it's a bijection.

 

[Mr Davis 97]

Formally also with a numbering. In this example it's only more work to do it, such that it's a bijection.

Could a sufficient proof be that, looking at the edge set, we have $(v-1)+(v-2) +1 = 2(v-1)$ elements?

 

[member 587159]

Could a sufficient proof be that, looking at the edge set, we have $(v-1)+(v-2) +1 = 2(v-1)$ elements?

Yes, that's perfectly fine. I doubt an instructor would ever ask to set up a bijection when it is obvious as in this case.