Thread: Graph theory

1.Is there a graph with degrees 1,2,2,2,3,3,4,4,4,5,5,7,7?
2.Is there a bipatite graph with degrees 3,3,3,3,3,5,6,6,6,6,6,6?
3.Is there a simple graph with degrees 1,1,4,4,4,6,6,7,8?

Either give such a graph or prove that no such graph exists.


(2)
(i)For each of the graph in figure 10.5, label the vertices and edgrs and write down the adjacency matrix of the graph.
(ii)Let G be any bipartite graph whose vertex set is partitioned into the subset{v1,v2,v3,...,vn}and{w1,w2,w3,...,wn}. What can you say about the adjacency matrix of G?


/I try do it but I can't./

Hello,

1. This is how I would do the first one :
What you have to do is to try to reduce degrees gradually until you get a sequence of degrees which obviously are the degrees of a graph, for example (0,0,0,0,0). So, what we're actually doing is deleting the last degree , and then we subtract 1 from as many members as was the last number of sequence (the one that you 'deleted'). Also, you keep the sequence sorted all the time, like in the beginning. In your example it will be:

(1,2,2,2,3,3,4,4,4,5,5,7,7) ----> (1,2,2,2,2,3,3,3,3,4,4,6)
(1,2,2,2,2,3,3,3,3,4,4,6) ----> (1,2,2,2,2,2,2,2,2,3,3)
(1,2,2,2,2,2,2,2,2,3,3) ----> (1,1,1,2,2,2,2,2,2,2)
(1,1,1,2,2,2,2,2,2,2) ---> (1,1,1,1,1,2,2,2,2)
(1,1,1,1,1,2,2,2,2) ---> (1,1,1,1,1,1,1,2)
(1,1,1,1,1,1,1,2) ---> (0,0,1,1,1,1,1)
(0,0,1,1,1,1,1) ---> (0,0,0,1,1,1)
(0,0,0,1,1,1) ---> (0,0,0,0,1)

We got (0,0,0,0,1) which means that your sequence doesn't represent degrees of a graph. You can prove it in 2 ways: either showing that graph with 5 vertexes cannot have only one with degree 1, because every edge needs 2 vertex. Or you can just continue with this proces and show that in the next step you will get (-1,0,0,0), which is of course impossible, because vertex cannot have negative degree.

Originally Posted by calfever

1.Is there a graph with degrees 1,2,2,2,3,3,4,4,4,5,5,7,7?

Heard of the most basic result of Graph Theory? The "handshake lemma"?

where . If the graph above is then . See a problem?

Originally Posted by Drexel28

Heard of the most basic result of Graph Theory? The "handshake lemma"?

Yeah, it's definitely much better way to solve the problem! : ))
However, in those examples where the sum is an even number, I think it's the best and quickest way to use the first method..

well, the first and third of the first assignment are pretty easy as the others stated...
the second is just as easy, though the "first method" can't be applied here because the graph is bipartite which means some vertices CAN'T have edges to some other vertices. what you need to do is find a way such that the sum of the x-vertices' degrees equal to the y-vertices' degrees since each edge go from x to y and hence adds 1 to both. there's no way to do that with those degrees (the 5 screws it up), hence no, there is no such graph.

2 (i) is easy, just label them and do an adjancy matrix...
Adjacency matrix - Wikipedia, the free encyclopedia

(ii) as i said before, the sum of the degrees of v1..vn equals the sum of the degrees of w1..wn.

for problems 1. 2. 3. I can do.


(2)I can do an adjacency matrix but I suspect that method that do the adjacency of graphs(null graph,complete graph) same as the adjacency matrix of a bipartite graph?????

I want example an adjacency matrix of a bipartite graph.

thanks a lot.

well, here's the adjacency matrix for 2(i)a):

0 1 0 1 0 0 0 0 0
1 0 1 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0
1 0 0 0 2 0 1 0 0
0 1 0 2 0 2 0 1 0
0 0 1 0 2 0 0 0 1
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 1 0 1
0 0 0 0 0 1 0 1 0

i started from left to right, top to bottom.