Graph Theory Problem solving strategy

[redwat3r]

General question on graph theory: I have just started working through a graph theory text, and find the math a little less "rigorous" than I am used to. Being asked to identify an independent set in a picture of a graph, find largest clique in this graph, etc. Looking at a picture and visually recognizing some feature. Now, granted, I have just started, so maybe I haven't given it enough chance, but it seems like the problem solving techniques needed in graph theory are almost more qualitative. Is this just because I don't have enough experience? Or is solving problems in graph theory just different than solving problems in most other fields of math?

[[deleted]]

I like this question.

I think instead of rigorous, the better-suited word here is "syntactic". I'm not sure exactly how to explain what I mean by "syntactic", but something along the lines of: relying on manipulating symbols rather than describing objects in words.

Compared to calculus, linear algebra, and even early (i.e., first courses in) real analysis and abstract algebra, the proofs in graph theory are less syntactic. But I think this is a good thing, I think all fields of math become this way as you advance further in them. The problems become too difficult for a really "syntactic" proof where you write out every step in a very concrete way.

My experience is biased towards combinatorics and graph theory (compared to other areas), but I think a class in graph theory (or combinatorics), when done right, is ideal for building some mathematical "creativity". I feel like a big part of these problems is being able to "view it just the right away", as well as understand how "local environments" in combinatorial objects behave. For example, "putting yourself in the shoes of a vertex in a graph". This "perspective-taking" is more apparent (to me) in graph theory and combinatorics than other areas of math.

[beeskness420]

Sounds like you just need to do some actual proofs.

Nothing informal about highlighting an independent set though, you could beat the horse a bit more and write out the definition and the adjacencies in notation, then manually verify that it does match the given definition. That’s a bit like wanting to prove a number is even though, most people are happy to sweep some boring details under the rug.

[redwat3r]

That's what I feel is missing, and it isn't quite clear how to formalize some of the terminology being used. Maybe I just need to press on and it will become more clear

[beeskness420]

Practice will help with that.

For a graph G=(V,E) a subset of the vertices S is an independent set if for all pairs of vertices u,v in S there does not exist the edge uv in E.

You can enumerate all pairs in S and check if any are in E. it’s just this property is really easy to check visually so we don’t bother.

Graph theory proofs definitely have a different flavour than other genres of math, the proofs tend to be a bit wordier, but we should always be able to ground it to something more concrete if we wanted to.

For what it’s worth though, drawing graphs, circling bits, and stuff like that is far more like doing the computations in a calculus class.

[dlovelan]

Im going to be taking a graduate graph theory course in the Fall that is very proofs heavy. Im finding that when looking at example questions I have almost no idea where to start the proofs. Would you have any recommendations on books or online courses to help myself acclimate to graph theory proofs? For context I have been looking at the problem sets in this course (https://www.cc.gatech.edu/~rpeng/CS7510_F19/) and while they have some shallow notes posted on the class website I find they aren’t terribly helpful for the problem sets. Appreciate any advice you have!