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

1
vote
1answer
75 views

If $\Delta(H)\leq 3$ and $H$ is a minor of $G$, then $H$ is a topological minor of $G$.

If $\Delta(H)\leq 3$ and $H$ is a minor of $G$, then $H$ is a topological minor of $G$. The converse follows by definition. However, most sources state this proposition without a proof. Any help is ...
2
votes
2answers
39 views

Graph with $k$ components.

Let $G$ be a simple graph on $n$ vertices. If $G$ has $k$ components and every component is complete prove that: $$|E| \le \frac{(n-k)(n-k+1)}{2}$$ I'm asking for advice.
1
vote
1answer
57 views

Find subgraphs in a directed graph which are isolated by edge properties

Please excuse my small knowledge of graph theory vocabulary. I can only describe the problem with common english words. Maybe someone can point me into the right direction and/or terms to look up. ...
2
votes
1answer
25 views

total number of triangles in $G$ and $G^C$

Prove that if G is a simple k-regular graph on n vertices then the total number of triangles in $G$ and $G^C$ is : $n\choose 3$-$nk(n-k-1)/2$. I can understand how $n\choose 3$ comes but doesn't it ...
4
votes
2answers
767 views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
5
votes
1answer
305 views

Number of Spanning Trees in a certain graph

Let $k,n\in\mathbb N$ and define the simple graph $G_{k,n}=([n],E)$, where $ij\in E\Leftrightarrow 0 <|i-j|\leq k$ for $i\neq j\in [n]$. I need to calculate the number of different spanning trees. ...
0
votes
1answer
37 views
1
vote
1answer
19 views

Graph Theory - Bipartite Matchings

Under what conditions can the symmetric difference between a (non-maximal) matching M and a maximal matching M* contain a path of length >= 2? The problem is to show that every vertex in the symmetric ...
1
vote
1answer
27 views

No.of faces in Peterson graph

I know that Peterson graph is not planar.But in this graph how can I determine the regions of the faces.How many faces does it include? Two faces can't include a common region right?
2
votes
1answer
17 views

Problem regarding maximum number of independent sets and maximum degree

Can someone please help me with this problem. Show that a graph with n vertices with maximum degree d satisfies $a(G)>=\frac {|V(G)|} {d+1}$, where a(G) is the ...
3
votes
1answer
437 views

Maximum cycle in a graph with a path of length $k$

I don't understand why this stands: Let $G$ be a graph containing a cycle $C$, and assume that $G$ contains a path of length at least $k$ between two vertices of $C$. Then $G$ contains a cycle ...
2
votes
1answer
313 views

Why does my Barabasi Albert model implementation doesn't produce a scale free network

I'm trying to implement the Barabasi Albert model to generate some scale free network matching a power law distribution of degree. I'm using a value $m = 2$ for the main parameter of the algorithm, ...
2
votes
1answer
69 views

Show that $\chi(G)+\chi(G')\ge2\sqrt n$

I want to show that $\chi(G)+\chi(G')\ge2\sqrt n$ where $G'$ is the complement of some graph $G$ of order $n$. I've so far managed to show $\chi(G)+\chi(G')\le n+1$ (probably not too useful) and that ...
2
votes
2answers
25 views

In any finite graph with at least two vertices, there must be two vertices with the same degree

Show that, in any finite graph with at least two vertices, there must be two vertices with the same degree. HINTS ONLY!
0
votes
1answer
26 views

graph theory problem on computer communication

Can someone please help me to do this problem: There are 1958 computers which can communicate among themselves in six languages with the condition that any two computers can communication with only ...
0
votes
1answer
37 views

A graph with diameter $2$

Suppose that we have a graph $G$ having $n$ vertex with diameter $2$ , Let $M=max\{deg(v_i) \}$ where $v_i$ are vertex of $G$ then $M\geq n-3$. I just made up this. It can be wrong but I could not ...
0
votes
0answers
71 views

Complexity of graph radius algorithm

I am a bit new so I hope I don`t break any rules. I have an algorithm: Given H = (V, E) a graph. If v ∈ V and r ∈ N, we will note with SH(v, r) the sphere of radius r with the center in v: SH(v, r) ...
1
vote
1answer
64 views

Pullbacks and pushouts in the category of graphs

Let $\textbf{Grph}$ be the category of simple, undirected graphs without loops, together with graph homomorphisms. Note that there need not be any homomorphisms between two graphs, for instance ...
-1
votes
1answer
56 views

Deleting maximal independent sets in graph

Consider an undirected graph $G=(V,E)$. The maximum degree of any vertex is $10$. A set $E'\subseteq E$ is called "maximal independent" if no two edges in $E'$ share a vertex, but adding any more edge ...
0
votes
1answer
32 views

Proving if planarity puzzle is planar

An "untangle" game app I have has scrambled planar graphs to be organized by dragging the nodes around until no lines cross. When solved, the puzzle is a lot of triangles. Some nodes have only 2 or 3 ...
0
votes
0answers
24 views

DFS runtime O(V) and O(E)

Here's a adjacency box diagram for DFS, Let nv = |V | and ne = |E|, i.e. nv is the number of vertices and ne is the number of edges in the input graph. Let's assume ne ≥ nv . I'm not quite sure ...
1
vote
1answer
42 views

Choosing well-connected set in directed bipartite graph

Consider a directed bipartite graph $G=(V,E)$. Can we always choose some set of vertices $V'\subseteq V$ such that no two vertices in $V'$ are connected by an edge, but any vertex in $V\backslash V'$ ...
0
votes
1answer
72 views

Finding chromatic polynomials of graphs in two ways?

Find the chromatic polynomial $c_{G}(k)$ by: relation $c_{G}(k) = c_{G−e}(k) − c_{G/e}(k)$ principle of inclusion and exclusion. The graph looks like a triangle of vertices a (top), b (right) , ...
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
39 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
14 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
30 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
29 views

search algorithm BFS?

So i have a recursive search algorithm here, ...
1
vote
0answers
39 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
65 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
20 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
30 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 ...