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
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.
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 ...
0
votes
1answer
18 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 ...
0
votes
1answer
37 views

How to demonstrate that $\chi(\bar G)=\omega(\bar G)$ , $G$ is a bipartite graph

If G is a bipartite graph then $\chi(\bar G)=\omega(\bar G)$?
1
vote
1answer
38 views

Is Dijkstra's algorithm optimal for unweighted graphs?

Dijkstra's algorithm is a very good approach to the shortest path problem. But is it optimal? Are there better algorithms for unweighted graphs?
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 ...
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
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 ...
2
votes
1answer
50 views

Find a recurrence relation for $h_n$. Let $h_n$ denote the number of spanning trees in the fan graph shown below.

Let $h_n$ denote the number of spanning trees in the fan graph shown below. Find a recurrence relation for $h_n$. I know it's got something to do with $h_n=F_{2n-1}$. But how else to find a ...
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) ...
4
votes
1answer
65 views

Graph Theory Question on Planar Graphs

How can it be proven that every planar simple graph is the union of three forests?
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?
-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 ...
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
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 ...
1
vote
1answer
63 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
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 ...
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 ...
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?
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 ...
1
vote
1answer
39 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'$ ...
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 \;; ...
0
votes
1answer
28 views

search algorithm BFS?

So i have a recursive search algorithm here, ...
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. ...
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 ...
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 ...
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 ...
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 ...
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
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, ...
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 ...
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 ...
3
votes
5answers
141 views

How do I succinctly note the sum of $(n-1)+(n-2)+…$?

I was playing with numbers and wanted to see how many possible connections there are in a network of $n$ nodes. I found that the answer was equal to ...
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 ...
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 ...
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.
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
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 ...