1
$\begingroup$

I am preparing for the exam of a first year introductory course on Graph Theory. 50% of the paper unfortunately consists multiple choice questions which are at times tricky. They do not necessarily test your computation skills or theory but just familiarity in general with known graphs. That is, my teacher likes to test us on the number of different graphs (under isomorphism) on a given vertex set satisfying given conditions.

A sample question would be how many different trees can be drawn on 4 vertices (2). This one is rather easy compared to some others and I constantly tend to overlook certain graphs.

Is there a list of drawn graphs with certain properties that I can just have a look at? Certainly don't intend to memorise it. Just to look through before the paper. Like the list on Wikipedia for Small Abelian Groups.

What I am looking for would be something like this:

For $|V(G)| = 4;$

There are x regular graphs, y trees, z self-complementary graphs etc.. with illustrations.

Any help is appreciated..

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, there are plenty such resources. This is the most useful one I know.

Moreover, I suggest you review important properties of graphs and the relationships between these properties. Usually, you'll be able to just "see" one of these properties, and then deduce the others by knowing the relationships/bounds. You need to know the relationships between all of the following:

  • Chromatic Number
  • Independence Number
  • Maximal Degree
  • Clique Number
  • Ramsey Number
  • Diameter

You should also look at important bounds, like Brooks' theorem, Moore's bound, the Handshaking Lemma, Cayley's Theorem, etc. Also, never forget the Petersen Graph. If there is any single graph you should know inside-out, it is this one.

$\endgroup$
2
  • $\begingroup$ I know. Have been studying the Petersen Graph. Is it too much to ask for a set of problems focused on the Petersen Graph? $\endgroup$
    – Ishfaaq
    Jan 2, 2014 at 0:37
  • $\begingroup$ Your graph theory textbook should have some, or you should be able to find plenty just by Googling! Good luck. :-) $\endgroup$
    – Newb
    Jan 2, 2014 at 0:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .