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

3
votes
3answers
154 views

Prove the condition of the score sequence make the tournament strong

Prove the theorem 4.19: A non-decreasing sequence $\pi:s_1,s_2,\ldots,s_n$ of nonnegative integers is a score sequence of a strong tournament if and only if $$\sum_{i=1}^ks_i > \binom k 2 $$ for ...
0
votes
1answer
44 views

One set dominating another in tournament

Consider a tournament with $799$ contestants. Each contestant plays against all other contestants exactly one; there are no draws. Prove that there exist two disjoint groups $A,B$, of $7$ contestants ...
2
votes
0answers
84 views

Connected graphs whose complements are connected

The complement of a disconnected graph is necessarily connected, but the converse is not true. For instance, $C_5$ is connected and isomorphic to its complement. The following picture shows a graph ...
1
vote
0answers
49 views

Euclidean Minimum Spanning Tree Property

Is the following statement about Euclidean MSTs true, and if so could someone help me with a proof? Between any two nodes, the EMST minimizes the maximum edge cost of any edge required to traverse ...
1
vote
1answer
94 views

Number of spanning trees for these 2 figures

The solution to the number of spanning trees of the graph below is given by $6$ and $4 \times 4 - 1$ for Graph A and B respectively. I'm not sure how to get this. Please assist. I did ask a similar ...
1
vote
1answer
74 views

Use of model theory in flag algebras

I need to learn about Razborov's "flag algebras" (see http://bit.ly/1u1a1NB) to solve a problem about graphs. Flag algebras are a very general new algebraic tool for studying combinatorial structures. ...
1
vote
1answer
167 views

Number of spanning trees of this graph

The solution to the number of spanning trees of the graph below is given by $3 \times 2 \times 3 = 18$. I'm not sure how to get this. Please assist. Thanks! Notes: Just in case anyone was ...
2
votes
1answer
33 views

confudes with Dijkstra's algorithm.

I have tried to understand the question but I got really confused. So starting from node 3, the distance to other nodes are 3 to 1 = 3 3 to 2 = 1 3 to 4 = 4 3 to 5 = 2 3 to 6 = 3 3 to 7 = 2 ...
0
votes
1answer
17 views

A discrete, linear graph at 45 degrees, where the N points add up to 1

I have a question: I have a set of points that represent a graph (x0,x1..x9) Lets say 10 points. They are at a linear 45 degree angle up (Gradient 1). I am also told that (x0+x1+x2..x9 = 1). How can ...
1
vote
1answer
45 views

prove that the only solution for the equation $L(G)=H \square K$ is $K=K_n$ ,$H=K_m$ and $G=K_{m,n}$.

suppose that $G$,$H$,$K$ are connected graphs with at least two vertices,prove that the only solution of the equation $L(G)=H \square K$ is $K=K_n$ ,$H=K_m$ and $G=K_{m,n}$. because the eigenvalue of ...
1
vote
2answers
62 views

If each pair of cities has exactly one direct one-way road between them, there is a path which visits each exactly once

Each pair of cities in a nation has exactly one direct one-way road between them. Show that there is a path which visits each city exactly once. Now, this problem seems ripe for induction, but I ...
3
votes
2answers
67 views

A simple $n$-regular graph with no cycles of length $>3$ has at least $2n$ vertices

Let $H$ be a simple graph that has no cycles of length more than $3$. Each vertex has degree of $n$. Is it possible to prove $H$ has at least $2n$ vertices?
2
votes
2answers
69 views

Chromatic Index Proof

We say that $G$ is $∆$-critical if $G$ is connected with $∆(G) = ∆$, $χ'(G) = ∆ + 1$, and $χ'(G − e) < χ'(G)$ for any $e ∈ E(G)$. Prove that if $G$ is $∆$-critical, then $d(x) + d(y) ≥ ∆ + 2$ for ...
2
votes
1answer
46 views

Choosing a committee from two people who are not sitting beside each other.

Assume that $10$ people are sitting around a table. Determine the number of ways to choose a committee, where the committee is made up of two people who are NOT sitting next to each other. Take ...
0
votes
1answer
48 views

Show that any connected graph $G$ satisfies $\lvert E(G)\rvert \geq \lvert V(G)\rvert -1 $

Show that any connected graph $G$ satisfies $\lvert E(G)\rvert \geq \lvert V(G)\rvert -1 $ by induction on the number of edges. My attempt: Base Case: For any connected graph $G$ let number of ...
0
votes
2answers
48 views

Maximum number of isomorphic graphs

Given a simple graph on $n$ vertices, how many graphs are atmost there that are isomorphic to the given graph? Is it $\Theta(n^2!)$ or $\Theta(n!)$ which is number of permutations of rows or columns?
2
votes
1answer
89 views

Does a colouring of a graph on two colours always have certain kinda of triangles

Is there a planar point set such that no matter how you colour the points with two colours can you can always find a triangle with exactly one point inside so that all four points have the same ...
0
votes
1answer
27 views

Maximum size of a clique

In doing a problem from graph theory by west. In one question it asks you to find the maximum sized clique in the graph. I think it's 5 (using the top or bottom vertex). However in the solution ...
2
votes
1answer
176 views

Give an example of 2 non isomorphic regular tournament of the same order

Give an example of 2 non isomorphic regular tournament of the same order I tried so many tournaments of the same order but got no luck, if they are regular, meaning all vertices of them have the same ...
0
votes
1answer
38 views

Prove that if $u$ and $v$ do not lie on a common cycle then $od(u)≠od(v)$

Let $u$ and $v$ be 2 vertices in a tournament $T$. Prove that if $u$ and $v$ do not lie on a common cycle then $od(u)≠od(v)$ I have no idea how to start this proof. Please help.
2
votes
1answer
43 views

Disagreement over Discrete Math Property

I know I'm probably wrong, maybe someone can explain it to me. I'm doing practice problems in preparation for a test that is coming up. Let u and v be two vertices in a graph G. Show that if G ...
1
vote
0answers
40 views

#edges of the graph for the legal moves of the rook in a chess board

Let's say $G$ is the graph for the legal moves of the rook in a chess board where the nodes corresponds to squares in the board; thus, there are 64 nodes present. I am trying to figure out #edges in ...
6
votes
0answers
82 views

Maximum number of cyclic quadruplets in tournament

Consider a tournament with $n$ contestants - that is, a complete graph directed graph $K_n$ where each edge is pointed one way or the other. We call a subset $\{a,b,c\}$ a "cyclic triplet" if each of ...
1
vote
0answers
38 views

prove this beautiful relation $ det(A^{*}_{m,n})=per(A_{m,n})$ .

suppose $P_n$ and $P_m$ are paths with $n$ and $m$ edges respectively.consider $A_n$ and $A_m$ as adjacency matrix of them.now I want to calculate the number of perfect matching of $P_n \square P_m$ ...
0
votes
1answer
63 views

What is meant by “connected components” in a graph?

I read the following statement : If the graphs $G$ and $G'$ are isomorphic then following is true: If $G$ is connected, so is $G'$. More generally, $G$ and $G' $ have same number of ...
2
votes
1answer
136 views

Show that for $2$ vertices $u$ and $v$ have the same score in a tournament $T$ then $u$ and $v $ belong to the same strong component of order $k$

a) Show that for $2$ vertices $u$ and $v$ have the same score in a tournament $T$ then $u$ and $v $ belong to the same strong component of order $k$ b) Prove that every regular tournament is strong ...
3
votes
2answers
153 views

Prove that every nontrivial tournament has at least one serf.

Serf definition: A vertex $z$ in a nontrivial tournament is called a serf if for every vertex $x$ distinct from $z$, either $x$ adjacent to $z$ or $x$ is adjacent to a vertex that is adjacent to ...
9
votes
2answers
6k views

Difference between a sub graph and induced sub graph.

I have the following paragraph in my notes: If $G=(V,E)$ is a general graph . Let $U\subseteq V$ and let $F$ be a subset of $E$ such that the vertices of each edge in $F$ are in $U$ , then ...
0
votes
2answers
30 views

Degree of a vertex in following graph.

If I have the following graph : Should the degree of vertex $v_2$ be 1 or 2...I'm asking this because I'm not sure whether loop should be counted while considering degree... (In my notes the ...
0
votes
1answer
61 views

Checking graph is simple or not ,given its degree sequence .

I don't know what is the way to check this: Check whether the graph having degree sequence $\{3,3,1,1\}$ is a simple graph or not? Please help explaining the strategy I must follow to check ...
0
votes
0answers
26 views

Suffix string starting at $i$

$S$ is the string of characters:TACGCGGT$ For string S and each of the positions $i=1,2,\dots,9$ write down the suffix string starting at position $i$. What is ...
0
votes
1answer
143 views

Is the number of simple circuits of a particular length preserved in two isomorphic graphs?

If two graphs are isomorphic, and one has a simple circuit of a particular length, must the other graph also have a circuit of the same length? Do they also have to have the same number of such ...
0
votes
1answer
26 views

Need help on an inequality proof

If G is a simple graph containing exactly two components H and H', show that $$|E(G)| \le \frac{(|V(G)|-1)(|V(G)|-2)}{2}$$ Here is my (incomplete) proof that I need help with: 1. Since H and H' are ...
2
votes
2answers
73 views

Determined those positive integers $n$ such that there exists a regular tournament of orders $n$

Determined those positive integers $n$ such that there exists a regular tournament of orders $n$ I know that a tournament is a oriented complete graph, and every complete graph $K_n $ has $ \left( ...
3
votes
2answers
450 views

How adjacency matrix shows that the graph have no cycles?

Let $G$ a directed graph and $A$ the corresponding adjacency matrix. Let denote the identity matrix with $I$. I've read in a wikipedia article, that the following statement is true. Question. Is it ...
2
votes
2answers
440 views

Is there any way, except trial and error, to find an isomorphism for these two graphs?

How can I tell that these graphs are isomorphic and how can I show it?
0
votes
1answer
55 views

Which Snake fields can be played infinitely long?

Snake is a very old game for phones. Its a 'real time game', that means you have to make decisions fast. The rules are: You are a snake. You can move to the left, to the right or go straight ahead. ...
0
votes
1answer
39 views

How are loops represented in an edge set?

When a node $v_1$ in a graph has an edge to itself (a loop), will this be represented as $\{v_1\}$ or as $\{v_1, v_1\}$?
4
votes
1answer
50 views

$4$-cycle of the same color in $K_n$

Let $k$ be a fixed positive integer. All edges of the complete graph $K_n$ are colored in one of $k$ colors. What is the least $n$ such that there always exists a $4$-cycle of the same color? This ...
0
votes
1answer
36 views

Given a random labelled simple graph with n edges, when is it more likely to get a graph with more edges than vertices?

That is, for what number of vertices n does there exists more simple labelled graphs (with n vertices) with more edges than vertices than simple labelled graphs (with n vertices) with more vertices ...
1
vote
1answer
63 views

dijkstra's algorithm in time O(k|V|+|E|)

Can somebody can help me with this problem: I have to calculate the minimum distance from a source node $s$ for undirected and connected graphs $G = ( V, E)$ with weights on the arcs belonging to the ...
0
votes
0answers
31 views

Expected number of distinct nodes visited in a directed bipartite graph

Let $G = (V,E)$ be a directed bipartite graph with $V = \{I \cup O\}$ where $\left\vert{I}\right\vert = n$ and $\left\vert{O}\right\vert = m$. All the edges start from a vertex in $I$ and end on a ...
0
votes
1answer
56 views

Probability that some that m points are probable given the probability of subsets.

Working in a problem in analysis I came across this combinatorial/discrete probability question. I would appreciate if someone knows how to approach this problem or knows if this problem is related ...
0
votes
2answers
65 views

Concept: The graph component

I have the following definition for a Component of a graph: A subgraph $H$ of a graph $G$ is a component of $G$ if $H$ is a maximal connected subgraph of $G$, ...
0
votes
1answer
206 views

Let $G$ be a simple graph whose vertices of maximum degree $\Delta $ induce a forest. Show that $\chi ^{'}=\Delta$.

Let $G$ be a simple graph whose vertices of maximum degree $\Delta $ induce a forest. Show that $\chi ^{'}=\Delta$. I actually don't understand this question well,is it saying that if we take induced ...
1
vote
2answers
245 views

Proving Konig-Egervary Theorem from Ford-Fulkerson

I've been going over a proof for Konig-Egervary Theorem from Ford Fulkerson, and I just don't see it. In fact, it just seems false. So I'm not sure what I'm missing. Note: the Konig-Egervary Thm says: ...
3
votes
0answers
98 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
2
votes
1answer
46 views

Prove or disprove a statement about $4$ regular graph with orientation

Prove or disprove: there eixsts a $4$-regular graph $G$ of order 7 and an orientation $D$ of $G$ such that for every vertex $u$ of $D$, there eixts either a $u-v$ path of length 1 or a $u-v$ path of ...
0
votes
1answer
158 views

How to prove that no hamiltonian cycle exists in the graph

** Show that the graph below has a hamiltonian path but no hamiltonian cycle. You can find more than one hamiltonian path such as $(b,a,c,f,e,g,d)$. Actually, I tried many times to find a ...
1
vote
1answer
84 views

Pidgeonhole Principle.

Suppose there are 3000 members in each of the club X, Y and Z. Each member from each of these three clubs has at least 3001 friends from the other two clubs altogether. Show that there are three ...