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

0
votes
0answers
21 views

HMM walk through for backward algorithm with given example

This pdf file is a resource that walk through a simple HMM algorithm of two states http://www.indiana.edu/~iulg/moss/hmmcalculations.pdf, I have question in step 4.1 of the algorithm Specifically ...
0
votes
0answers
22 views

Tree. Proof with induction.

The proof is taken from Introduciont to graph theroy. Wilson. Prove $T$ is a tree $\Rightarrow $ $T$ contains no cycle and has $n-1$ edges. If $n=1$ it's obviously. So let $2 \le n $ Since $T$ ...
2
votes
1answer
43 views

Graph Theory Question about People at a Party

Studying for final exams, I was given a practice question which goes as follows: There are (m − 1)n + 1 people at a party. Show that either there are m people, no two of whom know each other, or ...
0
votes
1answer
17 views

Graph theory - betweenness centrality in a bidirected graph

Say that I have a directed graph reflected by the following edgelist: 1 2 1 3 2 4 3 1 3 4 I wish to calculate the betweenness centrality of this graph. Note that there are ...
0
votes
0answers
27 views

question about omitting two petersen graph from $K_{10}$ .

prove that if we omit two petersen graph which has no common edges from $K_{10}$ we will get a cycle with 10 vertices which every two vertices which are in front of each other will be adjacent. ...
6
votes
1answer
117 views

Homework - Proof: Is this particular graph Hamiltonian?

I have a homework for my class to Combinatorics and Graphs which I'm not sure how to finish. The task: Let G be a simple graph on 14 vertices, with 4 vertices having degree 5 and 10 vertices having ...
1
vote
0answers
28 views

Prove that if $G$ is reconstructible, then $\overline G$ is reconstructible.

a) Prove that if $G$ is reconstructible, then $\overline G$ is reconstructible. b)Prove that every graph of order $n≥3$ whose complement is disconnected is reconstructible. For a), the book tell me ...
0
votes
0answers
11 views

Sufficient Condition for a graph to be Hamiltonian (HARARY)

I have a question for some parts of a theorem by Harary. Questions: 1.In the last paragraph, third sentence, how did the inequality $m<(p-1)/2$ follows and for its following sentence, why ...
1
vote
1answer
36 views

How many different perfect matchings are there in this graph?

Consider this graph: From the definition, a perfect matching of a graph with $2n$ vertices is a subgraph consisting of $n$ disjoint edges. The problems is I started counting them one by one and ...
0
votes
1answer
24 views

Existence of infinite subsequence of trees assuming two tree operations

Assume two operations on rooted trees: contract an edge: choose an edge $E$, join two vertices adjacent to $E$ grow a leaf: choose any vertex and connect it to a new leaf Starting with any rooted ...
2
votes
0answers
39 views

Prove that the property of being bipartite for a graph is recognizable.

Prove that the property of being bipartite for a graph is recognizable. Definition: A graphical parameter or graphical property is recognizable if for each graph $G$ of order at elast 3, it's ...
1
vote
1answer
57 views

Minimum number of edges to ensure connectedness

Question: Consider a simple graph G with n vertices. What is the minimum number of edges that G must have in order to ensure that it is connected? Justify your answer. My attempt: Let G = $(V, E)$. ...
15
votes
10answers
7k views

Graph theory software?

Is there any software that for drawing graphs (edges and nodes) that gives detailed maths data such as degree of each node, density of the graph and that can help with shortest path problem and with ...
0
votes
0answers
13 views

Fleury’s Algorithm in case of we have odd-degree nodes

I'm studying Fleury’s Algorithm to find Eulerian tour. I'm confused in case of we have two odd-degree nodes. What should we do in this case? Should we duplicate the path between the two add-degree ...
2
votes
1answer
28 views

Verify that R(p,2) = R(2,p) = p, where R is the Ramsey number

Verify that $R(p,2) = R(2,p) = p$, where $R$ is the Ramsey number It just seems obvious that $R(p,2) = R(2,p)$. But why do $R(p,2)$ and $R(2,p)$ both equal p?
0
votes
1answer
19 views

Prim's algorithm question

How to use Prim’s algorithm to find the minimal spanning tree for the following weighted graph, starting from the edge CE. What is the total minimum weight? Im confuse with this graph chapter as it ...
1
vote
1answer
24 views

Existence of infinite subsequence of trees with a subtree contained in the sequence

Assume a statement: For every infinite sequence of rooted trees $\{T\}_{i=0}^\infty$ there is an index $j\geq0$ such that there are infinitely many trees in $\{T\}_{i=0}^\infty$ which contains ...
0
votes
2answers
31 views

Assign integers to the vertices of $G$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less ...
0
votes
1answer
28 views

search algorithm BFS?

So i have a recursive search algorithm here, ...
1
vote
0answers
38 views

sum of chromatic numbers

How I can prove that in given simple graph G in n vertices: $$\chi(G) + \chi(\overline{G}) \leq n + 1.$$ Where $\chi$ is chromatic number. I tried to do like that: $$\chi(G) \leq \Delta(G) + 1 \;; ...
2
votes
0answers
64 views

existence of a spanning subgraph with min degree $\delta$ and at most $(n-1)\delta$ edges

Question: G is a graph with n$\ge$2 vertices an min degree $\delta$. Prove that G contains a spanning sub graph of a min degree $\delta$ with at most $(n-1)\delta$ edges. Thoughts: For the induction ...
1
vote
1answer
20 views

For a given finite group $Г$ , determine an infinite number of mutally nonisomorphic graphs whose groups are isomorphic to $Г$.

For a given finite group $Г$ , determine an infinite number of mutally nonisomorphic graphs whose groups are isomorphic to $Г$. I know that $Г$ is generated by $\Delta$ and for any finite $Г$, there ...
0
votes
1answer
19 views

Find all solution to the deck of following card

Find all solution to the deck of following card there is 7 cards, so I know that the graph $G$ has order $n=7$. Let $m_i$ be the size of $G-v_i$ for $1 \leq i \leq 7$ then $$m=\frac{\sum_{i=1}^n ...
3
votes
0answers
30 views

Upper bound for the sum of chromatic number of a graph and chromatic number of its complement

I need to prove that for any simple graph $G$ on $n$ vertices the following inequality is true: $\chi(G)+\chi(\overline {G}))\le n+1$; where $G$ is a simple graph, $\overline{G}$ its complement, ...
1
vote
1answer
23 views

Proof that a bipartite graph cannt exist with this degree sequence

Is there a bipartite graph with degree sequence $3,3,3,3,3,6,6,6,6,6,6,9$? Answer is No.Here's my justification: Suppose there exists such a bipartite graph G with the given degree sequence.And ...
3
votes
1answer
100 views

The graphs in which radius is equal to diameter

I was working out on a problem. Came out with a result in $C_n$: radius = diam. Worked out on other few graphs where radius=diam. Can we generalize the result? A little hint will be helpful. The ...
3
votes
1answer
29 views

Infinite graphs satisfying a certain Ramsey property

Let $G$ be a countably infinite graph. If $G$ has cliques of arbitrarily large finite size, then $G$ satisfies the following property, which I will call $(*)$: for any $r\in \mathbb{N}$ and any ...
1
vote
1answer
52 views

on the color classes of a $k$ chromatic graph

Let $G$ be a graph wich is $k$-chromatic. Suppose we have a coloring $(V_1, \ldots, V_l)$ such that each $V_i$ contains at least $2$ elements. I want to prove that $G$ has a $k$-coloring with this ...
0
votes
1answer
11 views

Finding nodes with a particular weight in a graph

Given a weighted graph $G=(V,E)$ and given two integers $n$ and $k$, I want to find (if they exist) $n$ nodes such that the sum $S$ of all the edges incident to such $n$ nodes is smaller than $k$. Of ...
0
votes
1answer
23 views

Expressing a hypercube subset definition using set notation

The definition of a hypercube is this: The $n $-dimensional hypercube $Q_n$ is the graph with $V = \left\{{ (e_1,\dots,e_n)|e_i \in \left\{{0,1}\right\}(i=1,\dots,n)}\right\}$ in which two ...
0
votes
1answer
28 views

Graph Theory. Induction Hypothesis.

I would like prove that: A graph contains an Eulerian cycle if and only if the graph is connected and every vertex has even degree. I'm going to try this by induction. How I can formulate the ...
1
vote
1answer
37 views

What would a Steiner tree look like for the vertices of a heptagon?

As it happens, I am currently frantically writing loads and loads of words for NaNoWriMo. One of the chapters I will be writing tonight essentially has the characters approximate a Steiner tree on ...
0
votes
0answers
19 views

Determine the group of color preserving automorphism for the Caley color graph $D_∆ (Г)$ of following graph

Determine the group of color preserving automorphism for the Caley color graph $D_∆ (Г)$ of following graph My professor did this example in class and he got following group of color In order to ...
3
votes
1answer
38 views

Show that Peterson Graph has no 7 cycle

In order to prove that Peterson graph has no 7 cycle I read the proof given in http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf The given proof is ...
0
votes
0answers
36 views

Graph Algorithms

Can someone prove that the total number of partial trees of a given complete graph Kn, which doesn't contain a fixed edge e ∈ E(Kn) is (n-2)*n^(n-3), where n >= 3, n ∈ N.
0
votes
1answer
25 views

How many possible 2-colorings of a disconnected bigraph?

Is there a relationship between the number of connected components in a bigraph and the number of possible 2-colorings? A connected bigraph (i.e. only one component) can be 2-colored in exactly two ...
3
votes
5answers
194 views

Halting probability of random tree-generating algorithm

Suppose I have a tree-generating algorithm as follows. Begin with one root vertex. With equal probability, create either three subvertices or none. Recurse and repeat for each of the subvertices (if ...
0
votes
1answer
23 views

Proof for k-connectedness of random graphs

I am really new to the theory of random graphs. It seems a lot of articles take for granted that: For $k\in\mathbb{N}\setminus\{0\}$ and $p\in(0,1)$ fixed, almost every graph in $G(n,p)$ is ...
0
votes
2answers
36 views

games in a round-robin tournament

How many games are played in a round-robin tournament held with n tennis players where each of the players will play against every other player exactly once. The answer is $\frac{n(n-1)}{2}$. What ...
0
votes
1answer
24 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
0
votes
1answer
45 views

Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

Let G be a simple graph with 25 vertices and 6 connected components. Find (i) the minimum number of edges that G can have. (ii) the maximum number of edges that G can have. What I know: The maximum ...
-1
votes
0answers
44 views

No perfect matching of k-regular graphs

For each $k\geq 2 $, find a $k$-regular graph that has no perfect matching. I found a link similar to this question but I am not familiar with the terminology, for example "$1$-factor". Is ...
0
votes
1answer
31 views

Bipartite Graph and Non-connected node?

Is this one bipartite graph or not? It is a simple question for you but i can't find the answer.
1
vote
1answer
53 views

Number of $q$-colorings of an $n\times n$ grid graph without adjacencies

Suppose a square grid graph $g$ of side length $n$ can be colored with $q$ colors. In how many unique colorizations are no adjacent vertices the same color? A friend and I have been trying to find a ...
0
votes
2answers
36 views

Proof. Theory graph. Please check.

If graph $G = (V,E) $ where $|V| = n $ is connectivity then $ n-1 \le |E| $ My proof: The our thesis is: $ \forall G $ is connectivity $\Rightarrow$ $ n-1 \le |E| $ I prove that using 'reductio ...
2
votes
2answers
35 views

Number of length-n paths in a graph with a fixed start vertex

So I was looking at a few past-years' papers from the ZIO (an IOI qualifier held here in India), and I found this question: I think this is the same as finding the number of paths of (let's take (a)) ...
0
votes
0answers
29 views

Planar graph is bipartite iff its dual is Eulerian?

I know this theorem is true, but if the dual of the graph is not simple, i.e. a multigraph, how does that effect the result? Does this still work if the Eulerian graph is a multigraph and its ...
1
vote
1answer
5 views

Name for “Stratified” or “Synchronized” directed acyclic graph?

This may be a stupid question, but is there a name for a directed acyclic graph in which: every node can be organized into separate, sequential "bins" any two adjacent "bins" of nodes are a (not ...
1
vote
1answer
24 views

Number of spanning trees for this graph

Find $\tau(G)$ for the graph $G$ below. This is what I tried so far: Let $e$ denote the horizontal edge between the two vertices as shown below. I wanted to use $\tau(G) = \tau(G-e) + \tau(G \circ ...
0
votes
1answer
16 views

prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6

Question: prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6. My proof: By induction. For n=7, the number of edges is 21=$2 ...