4
votes
0answers
35 views

Number of $K_{10}$ always increases

Let $G=(V,E)$ be a graph with $n\geq 10 $ vertices. Suppose that when we add any extra edge to $G$, the number of complete graph $K_{10}$ in $G$ increases. Show that $|E|\geq 8n-36$. [Source: The ...
1
vote
1answer
38 views

Proportion of asymmetric graphs

Wikipedia states, that the proportion $$p(n):=\frac{number\ of \ asymmetric \ graphs \ with\ n\ nodes}{number\ of\ graphs\ with \ n\ nodes}$$ satisfies $$\lim_{n->\infty }p(n)=1$$ I wonder ...
0
votes
0answers
18 views

Partition in graph connecting itself and other half

Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta>10$. Prove that there is a partition of $V$ into two disjoint subsets $A$ and $B$ so that $|A|\leq ...
0
votes
0answers
26 views

Modified Graph Coloring Problem

Imagine I have a graph that I'm trying to color with two colors, white and black, except unlike the normal graph coloring problem where you say no two vertices of the same color can be adjacent, I ...
1
vote
0answers
16 views

How can you tile this checkerboard with trominoes? [duplicate]

Ok, so define a tromino as a $1$x$3$ tile. If a corner is removed from an $8$x$8$ board, is it possible to tile it with these trominoes? So far, I have concluded that you would need $21$ trominoes to ...
2
votes
1answer
47 views

Number of unlabeled simple graphs with $n$ nodes even for all $ n\ge 5$?

The extended version of OEIS for the number of unlabeled simple graphs with $n$ nodes shows that the only odd number (besides the trivial cases $n = 0 $ and $n = 1$) is for $n=4$ ($11$ graphs). The ...
2
votes
1answer
33 views

On the number of cycles and independent edges in $K_{8}$

I am trying to find the number of cycles and $K_{2}$'s in $K_{8}$. That is, partition $8$ into all the ways such that the lowest part can be a $2$, so we have $8 = 8$, $6+2$, $5+3$, $2+3+3$, $4+4$, ...
0
votes
1answer
30 views

Expression of the thresold with expected degree in a Random Geometric Graph

$n$ points ($P_i$) are distributed uniformly on the surface of an unit radius sphere. 2 points are interconnected if the distance between them is $\le r$ (thresold). We call the degree of point $i$ ...
5
votes
0answers
43 views

How can a finite graph be viewed as a discrete analogue of a Riemann surface?

In the paper "Riemann–Roch and Abel–Jacobi theory on a finite graph" by Baker and Norine, the first line of the abstract states: "It is well known that a finite graph can be viewed, in many respects, ...
2
votes
1answer
24 views

Covering one part of a bipartite set

Let $G$ be a bipartite graph with bipartition $A,B$ where $A$ consists of all 2-subsets of $[n]$, $B$ consists of all 3-subsets of $[n]$ and the edges are defined by the inclusion relation. I would ...
4
votes
0answers
40 views

Probabilistic counting inequality

I am reading a proof involving the existence of a property in a tournament (a directed complete graph). To make the proof work, we need to have $n^ke^{-n/2^k}<1$. Here $n$ is the order of the ...
1
vote
2answers
32 views

Is there a relationship between the clique of a graph and colouring of a graph?

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the ...
2
votes
0answers
23 views

Generalization of Kneser's graph

Let's consider subsets of the set $\{1,\dots,n\}$ which consist of $m$ elements. I wonder, what is the maximal number of such subsets such that cardinality of intersection of any two of them isn't ...
3
votes
2answers
57 views

Coloring Graph with some constarints

if Graph G be a Cycle with Length=4. how many ways we can color this graph with at most $\lambda$ different color, in such a way that non of two adjacent vertex has a same color?
1
vote
1answer
215 views

Is there software I can use to draw this graph?

So, I have this particular graph to consider. It has the vertex set $\{1,...,17\}$ and edge set $\{(i,j)|i+j ~\mbox{is prime}\}$. Define a cost function $c:E(G)\mapsto \mathbb{R}$ by setting ...
2
votes
0answers
32 views

What happens to the number of maximal cliques (and their size) as you delete one edge at a time from a complete graph?

Say one has a complete graph with 1 giant clique. As we delete an edge from it at a time, the number of maximal cliques might increase or at least, the size of the maximal clique has to decrease by ...
1
vote
1answer
50 views

Lower bound on counting perfect matchings in bipartite graph

Let $G=(V_1 \cup V_2,E)$ be a finite bipartite graph. If every vertex in $V_1$ has degree at least $r\le|V_1|$ and $G$ has a perfect matching, we want to show there are at least $r!$ complete ...
1
vote
0answers
11 views

Selecting one number from each set with minimum variance

I have a dataset that I need to find several sets of "similar" looking events across many days, which leads to the following problem. Suppose I have $N \sim 500$ sets, each containing $N_j \in [5, ...
2
votes
1answer
18 views

Round table arrrangement for 13 people using graph theory

13 Members of a new club ,meet each day for lunch at a round table. They decide to sit such that every memher has different neighbours at each lunch.How many days can this arrangement last? ...
0
votes
1answer
26 views

number of vertices a special graph

Suppose a tree G has exactly one vertex of degree i for each 2<=i<=m and all other vertices have degree 1. How many vertices does G have?
3
votes
2answers
96 views
+50

Question about the proof of Ramsey's Theorem

I was reading up on a proof of Ramsey's Theorem and I can't understand this part of the proof: Pick a vertex $v$ from the graph, and partition the remaining vertices into two sets $M$ and $N$, ...
5
votes
0answers
83 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
6
votes
1answer
72 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
2
votes
0answers
43 views

Cubic 3-edge connected graph has edge cover that can omit 2/3 of all edges over 5 graphs (so 2/15 per graph) and be 2-edge connected

Let's assume that I have a cubic 3-edge connected simple graph $G$. After taking a perfect matching (and we can specify which one we want), I want to split the remaining edges in 5 sets $U_1, ..., ...
2
votes
1answer
45 views

Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
2
votes
1answer
78 views

counting occurence of subgraphs by counting their occurence in larger subgraphs

I have a mental block in fully understanding the following notion. Let $G$ be a graph of order $n$ and $H$ a fixed small graph of order $k \le n$. Suppose that there are $d$ copies of $H$ as an ...
0
votes
1answer
38 views

How to prove the equivalence of 2 affine spaces given that one is the subset of the other one?

For the sake of completeness, I would like to give you some concepts before asking the questions: For every simplex $S=<<x^{0},x^{1},...,x^{k}>>$ in $\Bbb R^{n}$, denote by $H_s$, the ...
0
votes
1answer
68 views

Prove that the graph $H = H_1\cup H_2 = (V_1\cup V_2,E_1\cup E_2)$ is connected.

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
0
votes
1answer
292 views

provide a combinatorial proof that $C_{n+1} = C_0C_n + C_1C_{n-1} + …. + C_kC_{n-k} + …C_nC_0$

(a) Let $C_n$ denote the number of ways of writing a valid list of open and closed parentheses of length $2n$ (valid means that at any point along the list, the number of open parentheses must be ...
0
votes
1answer
30 views

Number of trees on a vertex set $\lbrace{1,2,\ldots,7\rbrace}.$

How many trees are there on the vertex set $\lbrace{1,2,\ldots,7\rbrace}$ in which the vertices $2$ and $3$ have degree 3, and vertex $5$ has degree 2, and all the others have degree 1. I proceeded ...
0
votes
0answers
38 views

Shape with 81 vertices and 810 edges

I have 81 points. Each one of them has to be connected to 20 others, which means there are 810 connections. How many different ways can I arrange each point to be connected to exactly 20 others?
0
votes
1answer
69 views

Prove that if all costs are proportional to distances, then a shortest tour cannot intersect itself.

Prove that if all costs are proportional to distances, then a shortest tour cannot intersect itself. If replacing two of the intersecting edge with two others edge that pairing up with the same ...
0
votes
1answer
30 views

Hall's marriage problem, graph theoretic version

Let $G = ( V,E)$ be a bipartite graph, where $V = V_1 \cup V_2$ , $|V_1| \leq |V_2|$ . For every $A \subseteq V_1$ let $\phi(A) $ be the set of vertices in $V_2$ adjacent to vertices in $A$. By ...
0
votes
1answer
51 views

Combinatoric Graph

Draw a graph whose nodes are the subsets of {a,b,c}, and for which two nodes are adjacent if and only if they are subsets that differ in exactly one element. (a) What is the number of edges and ...
1
vote
1answer
34 views

How many ways can we color a $7$-cycle with $3$ colors so that no three consecutive nodes are of the same color

I have to paint graph We have three colors. The constraint is that there are no three consecutive nodes of the same color. And my idea is: All ways to paint is $3^7$ I'm going to count ...
0
votes
0answers
21 views

Inclusion-wise minimal feedback arc set

How is the term inclusion-wise defined? More precisely, I am trying to get a hold of what an inclusion-wise minimal feedback arc set is. Let $G = (V,E)$ be a (directed) graph. A feedback arc set $F ...
0
votes
4answers
73 views

a 2-regular graph is cyclic or not?

We know the common result : - If every vertex of a graph G has degree at least2, then G contains a cycle. Can I conclude that 2-regular graphs are cycles where degree is exactly two of every vertex? I ...
5
votes
1answer
61 views

Counting graph isomorphisms and entropy

Question: If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like? Are there any patterns that emerge as ...
0
votes
1answer
28 views

Probabilistic method in coloring of graph

I was reading Noga Alon's Probabilistic Methods and came across this question which I am unable to prove. There is a two-coloring of $K_n$ where $K_n$ is a complete graph of $n$ vertices with at most ...
3
votes
1answer
92 views

Decomposing the Complete Graph into Forests

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility ...
1
vote
0answers
25 views

Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
1
vote
0answers
40 views

A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
1
vote
1answer
25 views

Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
3
votes
0answers
24 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
0
votes
0answers
53 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
1
vote
1answer
40 views

proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
-1
votes
1answer
112 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
1
vote
0answers
21 views

Gallai & Milgram path covers theorem from Diestel

I have a question about the theorem of Gallai and Milgram stating that every directed graph has a path cover $P$ such that one can make an independent set of $G$ by picking vertices from each of the ...
1
vote
0answers
17 views

How many graphs on n nodes, with each component a coherently directed tree

For a positive integer $n$ choose $m$ with $1 \le m \le n$ and let $X$ be a set with $|X|=n$. choose $x_j \in X$ for $j=1,...,m$. Define $m$ directed graphs $X_j$ in the following way: Initially we ...
1
vote
1answer
66 views

counting full bipartite matchings

My actual question is to find the number of transversal given a collection of set ... After a little bit of study it has come down to: How can we count the number of matchings in a bipartite graph ...