Graph Theory 2: Now featuring Squiggly lines!

Let’s start with the some better definitions. Last time I was talking about dots and lines, but the proper terms are vertices and edges so that is what I will use from now on. First we can look at the most basic graph possible, just one vertex with no edges.
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(2.5,2.5){\circle*{1}}  \end{picture}

It is a pretty uninteresting graph, so let’s just move on. If we have two vertices then we have two possible graphs. First:
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(1.5,1){\circle*{1}}  \end{picture}
And second:
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(1.5,1){\circle*{1}}  \put(1,1){\line(1,0){.5}}  \end{picture}
The first is disconnected, while the second is connected. Still pretty boring so again let’s move on to three vertices. Then we have:

\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(2,1){\circle*{1}}  \put(1.5,1.5){\circle*{1}}  \end{picture}
And
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(2,1){\circle*{1}}  \put(1.5,1.5){\circle*{1}}  \put(1,1){\line(1,0){1}}  \end{picture}
And
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(2,1){\circle*{1}}  \put(1.5,1.5){\circle*{1}}  \put(1,1){\line(1,1){.5}}  \end{picture}
But wait! Are these two graphs with only one edge between two vertices any different? No, they describe the same exact graph, but things are moved slightly. In fancy math language we would say that the two graphs are isomorphic (the same). In even fancier math terms we would say they are the same because we could relabel them if they had names, and make the graphs be the same. I should start using labels. Next up we have:
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(1,1.1){A}  \put(2,1){\circle*{1}}  \put(2,1.1){C}  \put(1.5,1.5){\circle*{1}}  \put(1.4,1.5){B}  \put(1,1){\line(1,1){.5}}  \put(1,1){\line(1,0){1}}  \end{picture}
Any other graph with three vertices and two lines will be the same (isomorphic) as this one by nature. That is, because we have so few options with only three vertices, there are not many distinct choices.
Lastly:
\setlength{\unitlength}{7cm}  \begin{picture}(5,5)  \put(1,1){\circle*{1}}  \put(1,1.1){A}  \put(2,1){\circle*{1}}  \put(2,1.1){C}  \put(1.5,1.5){\circle*{1}}  \put(1.4,1.5){B}  \put(1,1){\line(1,1){.5}}  \put(1,1){\line(1,0){1}}  \put(1.5,1.5){\line(1,-1){.5}}  \end{picture}

Every possible edge is drawn between all vertices, so there is nothing left to put in. In general when every possible edge is drawn, the graph is called a complete graph.
To sum up; with one vertex we had one possible graph, with two vertices we had two possible graphs, with three vertices we had four possible graphs.

It turns out that there are 11 possible graphs on 4 vertices and it is a very hard problem to find out the general number of graphs for a general number of vertices. So instead let’s look at some complete graphs.
The complete graph on 4 vertices would be:
\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \put(0,0){\circle*{1}}  \put(0,.1){A}  \put(0,0){\line(1,0){1}}  \put(0,0){\line(1,1){1}}  \put(0,0){\line(0,1){1}}  \put(0,1){\circle*{1}}  \put(0,.9){B}  \put(0,1){\line(1,0){1}}  \put(1,1){\circle*{1}}  \put(1.1,1){C}  \put(1,1){\line(0,-1){1}}  \put(1,0){\circle*{1}}  \put(1.1,0){D}  \put(1,0){\line(-1,1){1}}  \end{picture}
The complete graph on 5 vertices would be: (I figured out squiggly lines)
\setlength{\unitlength}{7cm}  \begin{picture}(2,5)  \put(0,.1){A}  \put(0,.9){B}  \put(1.1,1){C}  \put(1.1,0){D}  \put(1.6,.5){E}  \put(0,0){\circle*{1}}  \put(0,0){\line(1,0){1}}  \put(0,0){\line(1,1){1}}  \put(0,0){\line(0,1){1}}  \put(0,1){\circle*{1}}  \put(0,1){\line(1,0){1}}  \put(1,1){\circle*{1}}  \put(1,1){\line(0,-1){1}}  \put(1,0){\circle*{1}}  \put(1,0){\line(-1,1){1}}  \put(1.5,.5){\circle*{1}}  \qbezier(0,0)(.5,.5)(1.5,.5)  \qbezier(0,1)(.5,.5)(1.5,.5)  \put(1,0){\line(1,1){.5}}  \put(1,1){\line(1,-1){.5}}  \end{picture}
Some things to notice for complete graphs are that if there are N vertices, then each vertex has N-1 edges coming out of it. This is because if you look at any vertex, it has to hit all the other vertices, and if there are N vertices, then there are N-1 vertices not including the one you start at that need to be touched by edges.

Using this fact we can also figure out the total number of edges of a complete graph. Each vertex has N-1 edges coming out of it.
So if we have two vertices, each vertex has one edge coming out. But they are the same edge so if we just ad 1 + 1 = 2 it would be wrong. We have to divide the total sum by 2 to disregard counting the same edge twice.
If we have three vertices, then each vertex has two edges coming out.
A has 2 edges, i.e., the edge that goes to B and the one that goes to C
B has 2 edges, i.e., the edge that goes to A and the one that goes to C
C has 2 edges, i.e., the edge that goes to A and the one that goes to B
This gives ups 2 + 2 + 2 = 6 total edges. Notice that again we’ve counted every edge twice. This is because each edge touches two vertices, and we count it once for one vertex and once for the other vertex. So we just have to cut our total in half again (divide by 2).
6 divided by 2 gives us 3 total edges

In general if we have N vertices, we do the same process. Each vertex has N-1 edges, and each edge has to touch two vertices so we will count N-1 edges twice. So we will have N times N-1 for the total count, but we will need to divide by 2 again to get rid of the double counting. To sum this up we can say:
\text{\# of edges} = \frac {N(N-1)}{2}

Advertisements
This entry was posted in Graph Theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s