Math Is Fun Forum

sohcahtoa-n

Member

Registered: 2008-04-10

Posts: 1

need some major help.

Graph Theory
Let V={1,2,…,20} be the set of the first 20 positive integers. Consider the graphs whose vertex set is V and whose edge sets are defined below. For each graph, investigate whether the graph (i) is connected (if not connected, determine the connected components), (ii) is bipartite, (iii) has a Eulerian Trail, and (iv) has a Hamilton path.
a) {a,b} is an edge if and only if a+b is even.
b) {a,b} is an edge if and only if a*b is a perfect square.
c) {a,b} is an edge if and only if a-b is divisible by 3.

So. I think I could do it If I could get some help on HOW to do it? Maybe if someone can do 1 for me (there are 4 more not included here).

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: need some major help.

a)

(i) If adding two numbers gives an even number, then they must both be odd or both be even. Then, edges only exist between numbers of the same type, and so an even number and an odd number can never be connected. The connected components are:
{1,3,5,7,...,19}
{2,4,6,8,...,20}

(ii) A graph is bipartite if its vertices can be divided into two sets such that no two vertices in the same set have an edge between them.
If this graph was bipartite, then since 1 and 3 have an edge between them, they would have to go in different sets. However, 5 has an edge between both 1 and 3, and so there is no place it could go.
Therefore, the graph is not bipartite.

(iii) A Eulerian trail is a path that traverses each edge of a graph exactly once. Since the graph is not connected, there is clearly no Eulerian trail in it.

(iv) A Hamilton path is a path that goes to each vertex exactly once. As above, there is no Hamilton path here since the graph is not connected.

The other questions are largely the same, you just need to figure out what each graph looks like first.

---

Why did the vector cross the road?
It wanted to be normal.