Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

2
votes
1answer
226 views

Ramsey Number Inequality

I want to prove that: $$R(\underbrace{3,3,...,3,3}_{k+1}) \le (k+1)(R(\underbrace{3,3,...3}_k)-1)+2$$ where R is a Ramsey number. In the LHS, there are $k+1$ $3$'s, and in the RHS, there are $k$ ...
1
vote
0answers
134 views

Even edge sets and cut edge sets

A cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. This problem is two ...
3
votes
1answer
226 views

Let G be a bipartite graph all of whose vertices have the same degree d. Show that there are at least d distinct perfect matchings in G

Let G be a bipartite graph all of whose vertices have the same degree d. Show that there are at least d distinct perfect matchings in G. (Two perfect matchings M1 and M2 are distinct if M1 does not ...
8
votes
1answer
294 views

Why does this matrix have 3 nonzero distinct eigenvalues

Consider the $n \times n$ matrix $$A=\left[ \begin{array}{cccc} 0 & 1 & ... & 1 \\ 1 & 0 & & 0 \\ \vdots & & \ddots & \\ 1 & 0 & & 0% ...
1
vote
0answers
67 views

Corresponding Triangulations of an (n+2)-gon to n Segments Connecting n+1 Collinear Points

So I'm asked to count the number of ways of connecting n+1 collinear points with n line segments subjected to the following constraints: If the line is L 1) No segment passes below L. 2) Starting at ...
2
votes
0answers
96 views

The Edge Set Grown in Kruskal's Algorithm

Let G = (V, E) be a weighted, connected and undirected graph. Let T be the edge set that is grown in Kruskal's algorithm and stopped after k iterations (so T might contain less than |E|-1 edges). Let ...
8
votes
1answer
4k views

How does Tree(3) grow to get so big? Need laymen explanation.

I am not a mathematician but I am interested in big numbers. I find them to be really interesting, almost god-like. I am watching a series of videos from David Metzler on youTube. I have a basic ...
2
votes
0answers
48 views

Cycle of digraph with 16 vertices

Let $G$ be a simple digraph with $16$ vertices. Suppose that any $10$ vertices of $G$ form a cycle of length $10$. Prove that any $11$ vertices of $G$ also form a cycle of length $11$. Is this a ...
3
votes
4answers
462 views

Graph theory and computer chip design reference

Wikipedia says graph theory is used in computer chip design. ... travel, biology, computer chip design, and many other fields. ... Is there a good reference for that? I can imagine optimal way ...
-1
votes
1answer
139 views

Stationary distribution for different types of graph

This is a follow-up questions to posts: Stationary distribution for directed graph Stationary distribution for different types of graph The definition of stationary distribution in ...
2
votes
1answer
400 views

Minimum number of triangles a polygon of n sides belongs to

Let there be a regular n-sided polygon. A "minimalist" triangle is a triangle which has all vertices on vertices of n. let p be a point on this polygon. What is the minimal number of correct triangles ...
0
votes
0answers
40 views

Question on special graph

Suppose that $q$ is prime. We construct a graph as follows: the vertices are prime divisors of the numbers $(q-1)/2$, $(q+1)/2$ and $(q^{2}-1)/24$. Two vertices $r$ and $s$ are joined by an edge if ...
4
votes
1answer
262 views

If $G$ is a tree (a connected graph without cycles) then the rank of $B_G$ is exactly $n-1$.

Let $G$ be a graph with $n$ vertices, and let $B_G$ be its incidence matrix. Show that: If $G$ is a tree (a connected graph without cycles) then the rank of $B_G$ is exactly $n-1$. I try to use that ...
2
votes
2answers
169 views

What graph is this?

For my game I am trying to implement a continues world by interconnecting the nodes like below I beg your pardon for my bad drawings I don't know how to explain it but its NOT DENSE GRAPH It is ...
3
votes
0answers
329 views

Isomorphic graph and adjacency matrix

We know that two graphs are isomorphic iff their adjacency matrices are similar via a permutation matrix. But if the adjacency matrices are similar, does it imply the graphs are isomorphic? This ...
1
vote
1answer
52 views

Showing that if $\chi(G) = n$ then $G$ must be $K_n$

How should I go about trying to proof that if $\chi(G) = n$ then $G$ must be $K_n$? Hints anyone?
6
votes
3answers
6k views

Proof a graph is bipartite if and only if it contains no odd cycles

How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.
2
votes
1answer
64 views

superposition cycle

I am reading a bachelor thesis where one defines a superposition cycle (of a graph) is a cycle which also is a symmetric difference of two perfect matchings of that graph. I am wondering that if the ...
1
vote
2answers
217 views

chromatic number proof for $K_n$

So for proving chromatic number of $K_n$ is $n$, and I use the fact that the chromatic polynomial for $K_n$ is $\frac{k!}{(k-n)!}$, is it correct to state $n$ is the minimum number such that the ...
6
votes
2answers
184 views

Knots and graphs

Every knot gives rise to a number of 4-regular planar graphs - by regular projections onto the plane - which just have to be enriched by an over/under flag for every vertex to be able to reconstruct ...
0
votes
1answer
721 views

Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
2
votes
1answer
86 views

Find a graph on 8 vertices with a pair of psuedosimilar vertices

Can somebody give me an example of a graph G on 8 vertices such that G has a pair of psuedosimilar vertices? Or, is it not possible? If it is not possible, please do not give me a proof, as I would ...
4
votes
1answer
163 views

small circle inside embedding of complete graph in the plane

On the web, I found this beautiful drawing of the complete graph on 13 vertices: It is on the Geometry Daily tumblr page. A computer scientist drew a more interactive version up to about 40 ...
1
vote
0answers
42 views

Cactus graph representation of min-cuts — must the components be connected?

Suppose a graph $G$ has edge-connectivity $c$. The min-cuts of $G$ (the cuts of weight $c$) can be represented in terms of a cactus graph $H$. This is "well-known". Each vertex of $w \in H$ ...
3
votes
2answers
202 views

Large Clique is in P or NP-complete? P != NP for hypothesis

I need to find a solution to the following question: The problem to find a "Large Clique" is in P or NP-complete (assuming P != NP)? The "Large Clique" problem is the following: Given a graph G = (V, ...
3
votes
1answer
54 views

Graph Decomposition and graph factor

If a graph G is H-decomposable does it imply that G has H-factor?
1
vote
0answers
155 views

Two-commodity minimum cost flow with antisymmetric costs

I'm looking at a minimum-cost flow problem in directed acyclic graphs. We are given a DAG plus a cost function that maps an edge to a real-valued cost, and a capacity function that maps an edge to a ...
2
votes
1answer
107 views

Coloring edges of a k-ary tree

In simulating a binary branching random walk, I needed to find a proper way to color each walks, so that we could follow a particle for example from its birth time to the end of the simulation, see ...
1
vote
2answers
708 views

What is the relationship between Clique, Independent Set, and Vertex Cover?

I'm aware that Vertex Cover and Independent Set are complements of eachother, but I've also heard Independent Set referred to something in relation to Clique; I just don't recall what. It can't be the ...
27
votes
6answers
2k views

Motivation for spectral graph theory.

Why do we care about eigenvalues of graphs? Of course, any novel question in mathematics is interesting, but there is an entire discipline of mathematics devoted to studying these eigenvalues, so ...
14
votes
3answers
320 views

Integer sequences which quickly become unimaginably large, then shrink down to “normal” size again?

There are a number of integer sequences which are known to have a few "ordinary" size values, and then to suddenly grow at unbelievably fast rates. The TREE sequence is one of these sequences, which ...
4
votes
1answer
189 views

to find the distance

i am trying to find the power graphs of cycles $C_n$ and then calculation of distances between vertices. for cycles $C_n$ we can find power graphs upto power greatest integer function of n/2. Square ...
1
vote
1answer
166 views

High clustering coefficient and large average path length in one graph

Can somebody provide an example of a network with a high clustering coefficient and a large average path length? A visual representation of such a network would be great. No reason for asking, ...
8
votes
3answers
252 views

What kind of combinatorial problem is this?

Is there a theory from which the following problem comes? Does this type of problem have a name? Find the largest possible number of $k$-element sets consisting of points from some finite set and ...
1
vote
3answers
342 views

Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines.

Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines. I've been struggling with this exercise for some time, but I can't come up with a decent proof.
2
votes
1answer
193 views

Ramsey Number proof

I am trying to prove: $R(3,3,3,3)\leq 4(R(3,3,3)-1) + 2$ I am confused as to how one can go from a $4$ color problem to a $3$ color problem by multiplying and adding. edit: $R$ is the Ramsey ...
0
votes
1answer
93 views

Graph factorization

Theorem by Kano, Lee, and Suzuki: Every connected cubic bipartite simple graph has a $\{C_n:n\ge 6\}$-factor. If I have a graph, say $G$, that has $6k$ vertices and satisfies the assumption of ...
3
votes
1answer
44 views

Base case for an induction proof relating to cycle graphs

What should the base case be for an induction proof on a general property for Cn, cycle graphs? Would it be n=2 or n=3? Since n=2 is not a simple graph, I'm guessing it would be the cycle graph on ...
1
vote
0answers
70 views

Is there another way to define this kind of graph?

Let there be $3m$ (where $m$ is any counting numbers and $m\ge{2}$) copies of $C_4$. we denote each copy of $C_4$ as $C_4(i),\quad 1\le i \le 3m $. Let $v_j(i)\in V(C_4(i)),\quad 1\le j \le 4$ be ...
0
votes
1answer
100 views

Edge coloring graph vertices probability

How to show the following: Let $R(k,t)$ denote the Ramsey function, that is the minimal number $n$ so that if the edges of a complete graph $K_n$ on $n$ vertices are each colored red or blue, then ...
4
votes
1answer
119 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...
8
votes
1answer
136 views

A graph with $n+1$ vertices and a vertex of every degree $1\dots n$

Let $G$ be a graph with $n+1$ vertices. Suppose that for every $i=1,\ldots,n$ there is a vertex in $G$ of degree $i$. What is the degree of the other vertex (that is, what degree is repeated)? I know ...
4
votes
1answer
151 views

No induced ordered graph yields large clique/stable set in ordered graph

Let $H$ be the ordered graph with three vertices $v_{1}$, $v_{2}$, $v_{3}$ (in this order) and one edge $v_{1}v_{2}$. Prove that there exists $c > 0$ such that every ordered graph $G$ not ...
3
votes
1answer
112 views

Deducing that “the probability of the intersection is (or is not) the product of the probabilities” from knowledge about other intersections

Let $A_1, A_2, \ldots, A_n$ be a collection of events in a probability space. There are $2^n - n - 1$ subsets S of $\{1, 2, \ldots, n\}$ for which we may or may not have $P(\bigcap_{j \in S}A_j) = ...
1
vote
2answers
137 views

A multiple-part question about interpreting powers of the adjacency matrix of a graph

Suppose that we have a group of six people, each of whom owns a communication device. We define a $6\times 6$ matrix $A$ as follows: For $1\le i\le 6$, let $a_{ii}=0$; and for $i\ne j$, ...
-1
votes
2answers
141 views

Can two different graphs have the same complement?

If two undirected graphs are identical except that one has an additional loop at vertex $A$, do they actually have the same complement?
2
votes
3answers
801 views

Proof that a n-hypercube is n-vertex-connected

I'm new to graph theory, I'm finding it hard to get upon proofs. To prove: An n-hypercube is n-vertex connected. Approaches I thought: It holds true for n=2, so ...
2
votes
3answers
269 views

Enumerating Rooted labeled trees without Langrange inversion formula

I am wondering how to enumerate rooted labeled trees without the Langrange inversion formula. Because each tree is a collection of other trees, the recursive generating function becomes $$C(x) = x + ...
4
votes
1answer
609 views

How to prove the Mantel's theorem of graph theory 's bound is best possible?

The theorem state that every graph of order $n$ and size greater than floor function $\lfloor \frac{n^2}{4} \rfloor$ contain a triangle. I already know a proof of the number of the edge of graph ...
14
votes
2answers
633 views

In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard? For example: $M = 2, N = 2$, ans $= 6$ $M = 3, ...