Graph Theory
A tree is a graph(set of vertices and edges) with no cycles ( no loops), show that if all the degrees of vertices is odd then the number of edges is odd

- dan815

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- dan815

|dw:1442641065902:dw|

- zzr0ck3r

is this for finite graph?

- dan815

any graph i have like a proof but its not legit

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- zzr0ck3r

If so then we can use the fact that \(|E(G)=|V(G)|-1\)

- dan815

its not a critical tree

- dan815

i said begin with some vertex of odd degree
|dw:1442642252949:dw|

- dan815

oh i see okay i like that

- zzr0ck3r

First note that we must have a finite graph if we are to talk about parity in edges(unless we have infinite vertices and finite edges...stupid). We will assume it is finite.
Now,
\(\sum_{v\in V(G)}deg(v)=2|E(G)|\)
Since the sum of the degrees is an even number, it must be that there are an even amount of vertices (each degree is odd). So, since \(|E(G)|=|V(G)|-1\) for finite trees, it must be that \(|E(G)|\) is an odd number.

- dan815

what is the definitio nof a finite tree?

- zzr0ck3r

finite vertices

- zzr0ck3r

but in a tree finite edges mean finite vertices

- zzr0ck3r

And the edges must be finite to prove they are odd.

- zzr0ck3r

in general when we talk size of graph we talk about vertices
I think it is because you can have infinite vertices and finite edges but not the other way around

- dan815

induction to prove V(G)=E(G)+1

- dan815

for any tree

- zzr0ck3r

Yeah, or just start constructing one, and say "by induction obviously"... lol

- dan815

ok gotcha

- dan815

thanks

- zzr0ck3r

That one should be a main theorem for any section on trees in a graph theory book.

- zzr0ck3r

if not I am sure it is easy to find on google...
Normally I use strong induction on graph theory. I find it fits more often

- dan815

sometimes i feel like they care too much about thsee proofs like some of this stuff should not require a proof xD

- dan815

like if u are not making a cycle, u are adding one extra vertex for every single edge

- dan815

my prof should be happy with that statement itself -.-

- zzr0ck3r

writing correct proofs is important though :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.