# Graph theory

## Main Question or Discussion Point

I am planing to take a course in Graph theory at my university, but i have no idea what it is.

I want to take something that is ,to some extent, rigorous and interesting.

This is the course summary provided by my school :

Introduction to graph theory and its applications with an emphasis on algorithmic structure. Topics may include graphs, digraphs and subgraphs, representation of graphs, breadth first and depth first search, connectivity, paths, trees, circuits and cycles, planar graphs flows and networks, matchings, colourings, hypergraphs, intractability and random algorithms.

From what i read this is almost like a computer science course!

I wanted to get an opinion from someone who knows a bit about graph theory. Does this sound like something that is worth taking if im looking for something rigorous and mathematical?

What exactly is graph theory ?

From what i read this is almost like a computer science course!
It is very applicable to computer science. Graphs are particularly well suited for computer science because they are finite structured objects that easily model all kinds of real world problems.

Graph theory has a very number theoretic feel to it.

So, does this course sound like something worth taking, based on the course summary above ?

Homework Helper
"Graph theory has a very number theoretic feel to it."

I'm not sure what that means, but if you go far enough into graph theory you will need some group theory and topology - at least for graduate level courses.

Im not sure what that means either since, i have not touched number theory.

What do you think are some courses I should have handy, in order to tackle graph theory ?

Homework Helper
If this is a first course (I'm guessing it is, or you wouldn't have these questions) it will be self-contained. You'll see some counting methods used in proofs, and quick sketches will be used more often than, well, you can count - at least, that's my experience.

What do you mean by counting methods used in proofs ? and quick sketches ? Sorry, i`m oblivious as to what you mean.

As far as counting methods, probably permutations and combinations. A graph is a set of vertices, some connected by what are called edges. Counting is used in counting vertices or edges in certain proofs. Since this sounds like a beginner course in graph theory, you will probably just be studying different graphs and their properties. For example, something very easy that you will probably learn is: A bipartite graph is two-colorable. Of course you probably don't know what that means, but the vocabulary is something you will also learn. Perhaps a link with more information will help...

http://en.wikipedia.org/wiki/Graph_theory

Might touch some topics from combinatorics, game theory, statistics, and linear algebra. But yeah if it doesn't cover some topology and group theory the subject is boring and dry unless you are a computer science major.

Thanks a lot guys. The course descriptions given on my school website could be quiet vague and ambiguous.

Hopefully it covers some topology! I need all the help I can get on topological abstractions before I take real analysis.

pbandjay I already checked it out, but it seemed like technician jargon to me.

Perhaps

http://www.math.niu.edu/~rusin/known-math/index/05CXX.html [Broken]

Graph Theory works a lot with set theory, relation theory, combinatorics, some matrix algebra and algorithm complexity analysis. In an introductory course, all of the fundamentals (other than basic algebra) are typically introduced. Some courses in Graph Theory have Discrete Mathematics as a prerequisite.

--Elucidus

Last edited by a moderator: