/sci/ - Science & Math

>>7969855

Here's how to answer it (I won't give you exact answers - just knowledge/direction needed):

1) A graph is Eulerian if and only if every vertex has even degree

2) a)
rad=1 -> universal vertex.
rad=2 -> vertex u such that for every vertex v, either uv in E or uw, wv in E.

which we know NEITHER can happen in G, so for each u there exist some v such that for every other w, uv not in E(G) and (uw not in E(G) or wv not in E(G)
what effect does this have on G complement? (Basically consider every vertex u, then doing that you should be able to easily construct paths of length 1 or 2
to every other vertex from it using the property I just mentioned, but considering G complement - so non-adjacency implies adjacency. Just look at what the
logical negation of that statement about E(G) I gave)


b) Easy to come up with a counter-example. Hint: has a complete graph as a subgraph (or at least mine did)

3) Just try this by hand...

4) a) Just prove that if min degree >= 2 that there exists a cycle (trivial to prove), then apply it componentwise and for b) just use the n = m + 1 formula for trees (of which there are k of them if there are k components)

Did you even try? What were your attempts?