# Graph-theory questions

I am working on my homework about the graph-theory. I came across these questions of which im not sure what the answer is.

Q: Is it possible to draw the following graph without crossing lines? (plane)

A: No, this isn't possible it's only possible when there are an odd number of lines.

Q: Determine the number of spanning trees of the image above. A: I'm not sure how this works, since there are no weights attached. Are there 4 spanning trees since there are 4 points? Or are there 12 spanning trees, for every point its possible to go to three other points.

Q: What defines the row- and columnsum of an adjunctionmatrix in a directed graph? A: I really don't know.

Any help is appreciated,

Thanks

-
You can draw this graph without crossings. Imagine looking at a tetrahedron from the top. –  Louis Jan 13 '12 at 12:04
Or run one of the diagonals around the outside of the square: the lines are not required to be straight. –  Brian M. Scott Jan 13 '12 at 12:13

As was noted in the comments, this is a planar graph: it can be drawn in the plane without unwanted edge crossings. One elegant way was suggested by Louis: place three of the vertices at the vertices of an equilateral triangle, place the fourth vertex at the centre of the triangle, draw the sides of the triangle, and connect the central vertex to each of the corners.

There are quite a few spanning trees. Since there are four vertices, every spanning tree will have three edges (because in any tree, the number of vertices is one more than the number of edges). Those three edges must connect all four vertices, and they must not be a cycle. If you play with the graph for a while, you should see that there are two different kinds of spanning tree, snakes and claws. By a snake I mean a tree that can be stretched out into a linear graph, like this:

$$\bullet----\bullet----\bullet----\bullet$$

By a claw, I mean a tree in which all three edges meet at a common vertex.

Your graph has four claws, one for each of the four vertices, so the only hard part is counting the snakes. There are four snakes that use only the sides of the square: $\sqcup,\sqsubset,\sqsupset,\sqcap$. There are also snakes that use exactly two sides of the square. One looks more or less like the upper-case letter N, and another like the Cyrillic letter И; I’ll let you try to find the rest of them. Finally, there are snakes that use exactly one side of the square; one is $\ltimes$, and again I’ll let you try to find the rest.

In the last question I’m guessing that you mean the adjacency matrix of the graph. Suppose that $A=[a_{ij}]$ is the adjacency matrix of some directed graph with $n$ vertices, so that $A$ is an $n\times n$ matrix. The $i$-th row of $A$ is $$a_{i1}\quad a_{i2}\quad\dots\quad a_{in}\;,$$ where $a_{ij}$ is $1$ if there’s an edge from vertex $i$ to vertex $j$ and $0$ if there is no such edge. Imagine adding up these numbers one at a time. Your running total starts at $a_{i1}$; if it’s $1$, that’s because there’s an edge from vertex $i$ to vertex $1$, and if it’s $0$, that’s because there’s no such edge. Thus, at this point your running total is the number of edges leaving vertex $i$ and going to one of the first $1$ vertices. Keep going: your second running total is $a_{i1}+a_{i2}$. Can you see that this is the number of edges leaving vertex $i$ and going one of the first $2$ vertices? And that when you’re done, and your running total is the full total $a_{i1}+a_{i2}+\cdots+a_{in}$, it’s equal to the number of edges leaving vertex $i$ and going to one of the first $n$ vertices? But that’s all of the edges leaving vertex $i$, so it’s the out-degree of vertex $i$.

Now apply the same kind of reasoning to a column of $A$, say the $j$-th column; if you do it right, you’ll discover that the sum of the entries tells you something about vertex $j$.

-
Thanks for your help, explanation and effort you put in this answer! –  Jef Jan 19 '12 at 13:20
@Jef: You’re very welcome! –  Brian M. Scott Jan 19 '12 at 13:40

EDIT: Beaten to it by Brian M. Scott. But since our answers don't intersect much, I'll leave this here.

I think there are two things to note about your first question.

The first is that the edges of a graph do not have to be straight lines. This is because a graph $G = (V,E)$ is defined abstractly as a pair of sets $V$ and $E$, called the set of vertices and edges respectively, where $E$ consists of pairs of elements in $V$. The set $V$ could be anything; a set of integers, a set of sets, a set of breeds of dog. When we draw a graph, what we're really doing is creating a visual representation of the pair $(V,E)$, and so all we require of the representation of a particular edge (i.e. a line on the drawing) is that it somehow join the two relevant vertices. We could also define a particular graph by its drawing, but realise that distorting one of the lines in that drawing still defines the same graph (so long as it still connects the same two vertices).

Secondly, Kuratowski's Theorem (if this is relevant to you) gives conditions for a graph to be nonplanar: namely, it must contain a (subdivided) $K_{3,3}$ or $K_5$. In particular, a graph can't be nonplanar unless it has at least 5 vertices. To prove a graph is planar, we draw it in the plane without any crossings. To prove it is nonplanar, we find a subdivided $K_{3,3}$ or $K_5$. See Brian M. Scott's comment above for an example of how to draw your graph without crossings.

A spanning tree of a graph is a tree on all the vertices. I'm not sure if there's a standard way to count them, I hope someone will let me know if there is. Your graph is $K_4$. A tree is minimal connected (if we remove an edge from a tree, we disconnect it), so a spanning tree of this graph must have 3 edges. How many ways can we choose 3 edges from the 6 edges of the graph? Well, its $\binom{6}{3}$. But we must be careful, since not all of these are spanning trees: they do not all go through all 4 vertices, and they are not all maximal acyclic. So we need to subtract the number of 3-edge cycles the graph has (since these are precisely the 3-edge graphs that miss a vertex). It shouldn't be too hard to spot that there are 4, and so the final answer is $\binom{6}{3} - 4 = 16$. Alternatively, you could have used Cayley's Formula.

-
Thanks for your help and explanation! –  Jef Jan 19 '12 at 13:11