MHB What Are Key Strategies for Solving Discrete Math Graph Theory Problems?

AI Thread Summary
Key strategies for solving discrete math graph theory problems include understanding the concepts of graph complements, isomorphic graphs, and self-complementary graphs. It is essential to calculate the number of unordered pairs of vertices in a graph and apply this to determine the edges in the complement of a graph. Drawing graphs to visualize relationships and ensuring that transformations maintain isomorphism are crucial steps in problem-solving. Additionally, constructing explicit bijections can help prove properties like self-complementarity in specific graph configurations. Engaging with each problem individually and demonstrating effort in understanding the underlying principles will enhance problem-solving skills.
Physics news on Phys.org
First, I'd like to point out http://www.mathhelpboards.com/misc.php?do=vsarules #8: "Do not ask more than two questions in a post" and rule #11: "Show some effort". I recommend starting separate threads for problems 2–5 and describing what you have done and/or what difficulty you are having.

I'll give some hints about problem 1. For A, answer the following questions.

  1. How many (unordered) pairs of vertices does a graph with $n$ vertices have? Let's denote this number by $C(n)$.
  2. If a graph $G$ has $e$ edges, how many edges does the complement of $G$ have? Make sure you know what a graph complement is. The answer should use $C(n)$.
  3. What can be said about the number of edges in isomorphic graphs?
  4. Suppose a self-complementary graph with $n$ vertices has $e$ edges. Write an equation on $e$ using the definition of a self-complementary graph and points 2 and 3 above.

For B, draw a graph connecting each pair of vertices using either solid or dashed line. The number of edges of each type should be what you found in point A. The solid graph should be isomorphic to the dashed one. Put 4 vertices in the corners of a square. Make it so that rotating the picture by 90 degrees maps solid edges into dashed ones and vice versa. For 5 vertices, prove that a regular pentagon is self-complementary (construct an explicit bijection between vertices and check that it is an isomorphism).

For C, use the fact that $C(n)$ is an integer.
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...

Similar threads

Replies
5
Views
2K
Replies
4
Views
2K
Replies
4
Views
10K
Replies
2
Views
2K
Replies
3
Views
2K
Replies
1
Views
2K
Back
Top