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
5 views

Prove that graph $G$ is bipartite iff every $H\subseteq G$ has linearly independent group of vertices

Prove that graph $G$ is bipartite iff every $H\subseteq G$ has linearly independent group of vertices of size $\leq |V'|/2$. (where $G=(V,E)$ ,$ H=(V',E')$) I managed to prove the first part myself ...
1
vote
2answers
19 views

graph degrees question (combinatorics)

let it be $(d_1,d_2,...,d_n)$ which represents a series of positive integer numbers, so that $n\gt d1 \gt d2 \gt ... \gt d_n \ge 0$. let it be $K\ge d_1$. given that $(K,d_2,...,d_n,1,1...,1)$ ...
0
votes
0answers
17 views

Induction graph theory - dealing with reducing the problem

I have a general question regarding induction in graph theory. Often I am required to use induction in order to prove a theorm. I have seen a lot of cases in which the reduction of the problem was ...
0
votes
1answer
20 views

Kruskal's algorithm - Find the tree with the least possible weight

I need to find the tree with the least possible weight with Kruskal's algorithm. Here is my attempt: B-E-F-A-D and then I get stuck. Is my attempt looking correct? How should I continue?
5
votes
1answer
234 views

How to get from Chebyshev to Ihara?

I have competing answers on my question about "Returning Paths on Cubic Graphs Without Backtracking". Assuming Chris is right the following should work. Up to one thing: The number of returning paths ...
1
vote
0answers
10 views

cardinality of the maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...
1
vote
1answer
43 views

Does a $K_n$ with $n$ pendants have a name?

Consider the graph we get by taking the complete graph on $n$ vertices, and then attaching a pendant vertex to each of the $n$ vertices by an edge. Does such a graph have a name, i.e. do such graphs ...
0
votes
2answers
47 views

How do you find the value of n in this example

$$n^{n-2} = 16$$ I know $n = 4$ through trial and error but how do you find $n$ in a conventional manner? I'm basically trying to solve how many nodes are in a tree that has $16$ spanning trees ...
3
votes
0answers
17 views

Book recommendation for network theory

I'm looking for a mathematically rigorous book on Network theory covering topics like entropy, degree distribution, centrality, and regular, random, small-world and scale-free networks. I'm familiar ...
2
votes
1answer
54 views

How to find a maximum matching in this graph

Let's consider this graph: Now I take a matching M that only contains the edge 1. Clearly this matching is not maximum, because I can take the edge 3, so given that: We can easily notice that ...
1
vote
1answer
124 views

Eccentricity in corona product

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...
-3
votes
0answers
34 views

SimRank Example? [on hold]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
-1
votes
1answer
58 views

How to count the number of walks from $u$ to $v$ in a graph?

How can we count the number of walks on a graph from $u$ to $v$? Don't use : If $A$ is the adjacency matrix of the graph, then the $i,j$-entry of $A^n$ is the number of walks from vertex $i$ to ...
4
votes
2answers
2k views

How many connected graphs over V vertices and E edges?

Is there a way to calculate the number of simple connected graphs possible over given edges and vertices? Eg: 3 vertices and 2 edges will have 3 connected graphs But 3 vertices and 3 edges will have ...
0
votes
3answers
33 views

The difference between subgraph and component

I'm studying graph theory right now. I've been reading the textbook and searching the internet, but I still can't understand how subgraph and component are different. Aren't they basically referring ...
1
vote
1answer
25 views

Probability of dominating set in random balanced tournament

I'm trying to estimate some probability in a random tournament, and I know that what I have is false, as it leads to contradicting results published some 40 years ago. But I don't know where the ...
5
votes
1answer
427 views

The number of paths on a graph of a fixed length w/o repeatings

Sorry for bad English. Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$. But what if we can't walk through a vertex ...
-3
votes
0answers
15 views

Let $G$ be a simple graph that is not a forest and has girth $\ge 5$. Prove that the complement of $G$ is Hamiltonian [on hold]

Let $G$ be a simple graph that is not a forest and has girth with length of at least $5$. Prove that the complement of $G$ is Hamiltonian. (girth is the length of the shortest cycle of the graph)
3
votes
1answer
19 views

How to prove vertex-transitivity in regular graphs.

I have problems to prove wheter a regular graph is vertex-transitive or not. For instance, consider the following examples: the generalized Petersen graphs $P_{2,7},\;P_{3,8}$ and the Folkman graph. ...
0
votes
1answer
23 views

Ratio of degrees of nodes in Graph

I have a question regarding to graph and ratio of degrees of nodes in graphs. See the following image: I'm going to find a relation between $A$ and $C$. So, I count all links from $C$ to $B$s $= ...
2
votes
0answers
33 views

Counting Spanning Trees Needed to cover Edges

This is in the same spirit as this stackexchange post, but I am seeking a more general answer. The goal is, given a graph $G$, give a method of counting the minimum number of spanning trees needed ...
2
votes
1answer
26 views

How to answer this graph theory question?

Okay so let me define some terms before I ask my problem: Let $K_n$ denote the complete graph on $n$ vertices with $n\geq 2$ and let $C_3$ be a cycle of length $3$ (a triangle). Suppose $x,y,z$ ...
0
votes
0answers
26 views

A little bit more difficult problem regarding rooted plane trees

A question regarding rooted plane trees bothers me. We know that the number of rooted plane trees with $n$ nodes equals to $n-{th}$ Catalan number, that is $|Tn| = Cn$. But what is this number if we ...
1
vote
1answer
148 views

How many rooted plane trees tn are there with n internal nodes?

How many rooted plane trees tn are there with n internal nodes? Plane means that left and right are distinguishable (i.e. mirror images are distinguishable), and rooted simply means that the tree ...
0
votes
0answers
16 views

Eulerian circuit for connected graph with even degree vertices

Let $G$ be a connected graph where every vertex has even degree. Show that $G$ has an Eulerian circuit. Certainly the converse is true and is not hard to show.
3
votes
1answer
42 views

Class of graphs with symmetric random walk

Let $(V,E)$ be a graph and let $X_n$ be a random walk on the graph. At every step, the walker at $x$ jumps to one of the neighbors drawn uniformly at random among all the vertices $y$ such that there ...
0
votes
2answers
36 views

Computing expectation exercises; using linearity of expectation and iterator random variables

Disclaimer: This is homework that is overdue by, but I do want to understand it and get through it, so any hints or guidance is appreciated This is for an algorithms class currently dealing with ...
4
votes
9answers
4k views

Prove that every undirected finite graph with vertex degree of at least 2 has a cycle

Prove that every undirected finite graph with vertex degree of at least 2 has a cycle. Intuition-wise i need to prove that there's at least one 'tight -connection'. In other words, Proving that 2 ...
1
vote
1answer
34 views

Let $G$ be a graph on $n$ vertices, where $n \geq 3$. Suppose that $\Delta(G) \geq n/2$. Can $G$ have more than one component?

Let $G$ be a graph on $n$ vertices, where $n \geq 3$. Suppose that $\Delta(G) \geq n/2$. Can $G$ have more than one component? i did this for $n=3$ $\Delta(G) \geq 1.5$ as $\Delta.1$ component. for ...
1
vote
1answer
18 views

Graph Theory: Conditional Expected Value of Product of two Random Variables

Consider a graph with $n$ vertices, where each edge between any two vertices is independently drawn with probability $p$. Let $D_i$ be the degree of vertex $i$. What is $E[D_i \cdot D_j]$? Here is ...
3
votes
2answers
80 views

Finding all k-size subgraphs

I have no experience with advanced combinatorics, but I have to solve a problem that I think I will need advanced combinatorial techniques, correct me if I am wrong. Let $G$ be a large directioned ...
0
votes
0answers
37 views

The length of a shortest path from $u$ to $v$ in a connected graph $G$ equals the level of $v$ in any BFS tree of $G$ with $u$ as root

I am studying graph theory but I cannot solve this question. Can you help me? "The length of a shortest path from $u$ to $v$ in a connected graph $G$ equals the level of $v$ in any BFS tree of $G$ ...
5
votes
4answers
11k views

Prove two graphs are isomorphic

I have identified two ways of showing it isomorphic but since it is a 9 mark question I dont think i have enough and neither has our teacher explained or given us enough notes on how it can be ...
-1
votes
0answers
21 views

Is it true that any 20 regular graph has a path of length at least 10? [duplicate]

hi i am confused with this question."Is it true that any 20 regular graph has a path of length at least 10?" Does this make sense?
-1
votes
1answer
39 views

Can a graph with no cut edges contain a cut vertex [on hold]

hi can you help with this question. "Can a graph with no cut edges contain a cut vertex?"
0
votes
1answer
39 views

Graph Theory-Breadth First Search

I've been asked the following: Show that the length of the shortest path from $u$ to $v$ in a connected graph $G$ equals the level of $v$ in any BFS tree of $G$ rooted at $u$. I can't find any proof ...
-1
votes
0answers
39 views

Watts-Strogatz graphs

I'm stuck with this particular question. Can someone explain/help me? Suppose we construct a graph in $WS(n,k,p)$, starting from the n vertices in a ring, where each vertex is connected to its first ...
0
votes
1answer
15 views

If $G$ is a connected graph with $n$ vertices and$ n - 1$ edges then $G$ is a tree, using Induction.

I am still new to proof methods and not sure if this is the correct use of induction. Base case: $n = 1$ has $0$ edges and is a tree. Assume every connected graph with $k$ vertices and $k-1$ edges ...
2
votes
1answer
24 views

Understanding the set of neighbors of a set

For a graph G(V, E), the Hall's theorem states If for every subset X of V we have that |N(X)| ≥ |X|, then G has a perfect matching where N(X) represents the set of neighbors of the set X in G. ...
2
votes
1answer
292 views

Count ways to reach last layer

Consider directed graph which has $N + 2$ layers numbered from left to right by integers from $0$ up to $N + 1$. The leftmost ($0$) and the rightmost ($N + 1$) layers both contain only one vertex ...
2
votes
0answers
52 views

ER graphs, expected number of triangles incident to one vertex

I'm really sorry for this question. I'm new to a graph theory, and I hope you will help me to understand one statement. Consider $ER(n,p)$ graph with $n \geq 3$ and $p \in [0,1]$. The statement ...
-1
votes
1answer
60 views

Regular graph path length problem [on hold]

Is it true that any $20$ regular graph has a path of length at least $10$? Can anyone please help me? I think there is a shorter path, but I can't be sure.
0
votes
0answers
13 views

graph theory-Eulerian

Graph G all vertices are even degree,it is Eulerian.Let W be a longest trail then I prove that it is closed trail.Then,suppose W is not Euler tour.I am going to show it is wrong proof by contradiction ...
0
votes
0answers
12 views

Sample data for a social graph

I wanted to use my facebook friends to create a social graph with around 50-100 nodes just to analyse mutual friendships, however it seems in a recent version of their graph API they prevent ...
4
votes
4answers
8k views

Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
1
vote
0answers
26 views

When do a Regular graph has an odd eigenvalue?

Merely looking at adjacency matrix of a regular graph, without explicit calculation, can we decide that graph will have an odd eigenvalue or not? If regularity is odd, we are sure that it will be an ...
0
votes
0answers
23 views

tripartite graph with n vertices

What is the maximum number of edges in a tripartite graph with n vertices? a k-partite graph with n vertices? I know that bipartite graph has $\frac {n^2}{4}$ max edges
1
vote
0answers
9 views

Maximum number of transitive triples in 3-partite diconnected tournament

Show that if $T$ is strongly connected 3-partite tournament with partite sets $V_0,V_1,V_2$ then the maximum number of transitive triples is $|V_0||V_1||V_2|-1$, unless $|V_0|=|V_1|=|V_2|=2$, in ...
2
votes
2answers
2k views

Proof that any simple connected graph has at least 2 non-cut vertices.

I'm trying to prove that any simple connected graph with at least $3$ vertices ($|V| \ge 3$) has at least $2$ vertices whose removal will not lead to the increment of number of components. In other ...
1
vote
1answer
16 views

Proving that in a complete graph $\lambda(K_{n}) = \delta(K_{n})$

Since $K_{n}$ is n-1 regular. Then $\lambda(G)$ must be n-1. Since $\lambda(K_{n}) \leq \delta(K_{n})$ then by definition they must be equivalent. Can I use the definition or should I say since ...